BZOJ 1433 [ZJOI2009]假期的宿舍（网络流）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1433

【题目大意】

　　在校学生有自己的床，外校的则没有，如果两个同学相互认识，则可以借用他的床，
　　现在有些在校同学回家了，问留校的同学加上到来的外校同学，床位是否够用

【题解】

　　我们对于需要床位的同学从源点连流量为1的边，对于床位连流量为1的边到汇点，
　　在从i同学连到所有他能睡的床，流量为1，最大流等于需要床位的同学总数则说明可行。

【代码】

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

#include <cstring>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAX_V=1000;

struct edge{int to,cap,rev;};

vector<edge> G[MAX_V];

int level[MAX_V],iter[MAX_V];

void add_edge(int from,int to,int cap){

    G[from].push_back((edge){to,cap,G[to].size()});

    G[to].push_back((edge){from,0,G[from].size()-1});

}

void bfs(int s){

    memset(level,-1,sizeof(level));

    queue<int> que;

    level[s]=0;

    que.push(s);

    while(!que.empty()){

        int v=que.front(); que.pop();

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

            edge &e=G[v][i];

            if(e.cap>0&&level[e.to]<0){

                level[e.to]=level[v]+1;

                que.push(e.to);

            }

        }

    }

}

int dfs(int v,int t,int f){

    if(v==t)return f;

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

        edge &e=G[v][i];

        if(e.cap>0&&level[v]<level[e.to]){

            int d=dfs(e.to,t,min(f,e.cap));

            if(d>0){

                e.cap-=d;

                G[e.to][e.rev].cap+=d;

                return d;

            }

        }

    }return 0;

}

int max_flow(int s,int t){

    int flow=0;

    for(;;){

        bfs(s);

        if(level[t]<0)return flow;

        memset(iter,0,sizeof(iter));

        int f;

        while((f=dfs(s,t,INF))>0){

            flow+=f;

        }

    }

}

int T,a[60],n,x;

void solve(){

    int s=n*2+1,t=s+1;

    for(int i=0;i<=t;i++)G[i].clear();

    int tot=0;

    for(int i=1;i<=n;i++)if(a[i])add_edge(i+n,t,1);

    for(int i=1;i<=n;i++){scanf("%d",&x);if(a[i]&&!x||!a[i])add_edge(s,i,1),tot++;}

    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&x);if(x||i==j)add_edge(i,j+n,1);}

    if(max_flow(s,t)==tot)puts("^_^");

    else puts("T_T");

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        solve();

    }return 0;

}