P2055 [ZJOI2009]假期的宿舍

思路

看到复杂的匹配条件，发现要让一个人和一个床匹配，所以就每个有床的人（指本校学生）和t连一条边，每个需要床的人（指外校的人和不回家的人）和s连一条边，i和j互相认识就把i和j的床连在一起，自己和自己的床肯定连一条边，然后流量每多1，就表示满足了一个人对床的需求，跑最大流就相当于最多能满足多少人的需求，然后如果最大流大于等于需要床的人数，就可行，否则不可行

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 1000;

const int INF = 0x3f3f3f3f;

struct Edge{

    int u,v,cap,flow;

};

vector<Edge> edges;

vector<int> G[MAXN];

int cur[MAXN],s,t,n,dep[MAXN],vis[MAXN];

void addedge(int u,int v,int cap){

    edges.push_back((Edge){u,v,cap});

    edges.push_back((Edge){v,u,0});

    int cnt=edges.size();

    G[u].push_back(cnt-2);

    G[v].push_back(cnt-1);

}

int dfs(int x,int a){

    if(x==t||a==0)

        return a;

    int flow=0,f=0;

    for(int &i=cur[x];i<G[x].size();i++){

        Edge &e = edges[G[x][i]];

        if(dep[e.v]==dep[x]+1&&(f=dfs(e.v,min(e.cap-e.flow,a))>0)){

            flow+=f;

            e.flow+=f;

            edges[G[x][i]^1].flow-=f;

            a-=f;

            if(!a)

                break;

        }

    }

    return flow;

}

queue<int> q;

bool bfs(void){

    memset(vis,0,sizeof(vis));

    dep[s]=0;

    q.push(s);

    vis[s]=true;

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=0;i<G[x].size();i++){

            Edge &e = edges[G[x][i]];

            if(e.cap>e.flow&&(!vis[e.v])){

                vis[e.v]=true;

                dep[e.v]=dep[x]+1;

                q.push(e.v);

            }

        }

    }

    return vis[t];

}

int dinic(void){

    int flow=0;

    while(bfs()){

        memset(cur,0,sizeof(cur));

        flow+=dfs(s,INF);

    }

    return flow;

}

int cnt,is_stu[MAXN],is_stay[MAXN];

void init(void){

    cnt=0;

    edges.clear();

    for(int i=1;i<=MAXN;i++){

        G[i].clear();

    }

    memset(is_stu,false,sizeof(is_stu));

    memset(is_stay,false,sizeof(is_stay));

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        init();

        s=MAXN-2;

        t=MAXN-3;

        scanf("%d",&n);

        for(int i=1;i<=n;i++){

            scanf("%d",&is_stu[i]);

            if(is_stu[i])

                addedge(i+n,t,1);

        }

        for(int i=1;i<=n;i++){

            scanf("%d",&is_stay[i]);

            if((is_stu[i]&&(!is_stay[i]))||(!is_stu[i])){

                addedge(s,i,1);

                ++cnt;

            }

        }

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++){

                int x;

                scanf("%d",&x);

                if(i==j||x){

                    addedge(i,j+n,1);

                    continue;

                }

            }

        if(dinic()>=cnt){

            printf("^_^\n");

        }

        else{

            printf("T_T\n");

        }

    }

    return 0;

}