Mr Loser

题解 P2055 【[ZJOI2009]假期的宿舍】

2019-08-14 14:56:46


解题思路在代码中。

/*
* 我的思路:遇到需要住宿的人就让他和源点之间连一条容量是1的边;
* 如果是在校学生就把他的床和汇点之间连一条容量是1的边;
* 把每个不回家的在校学生和自己的床之间连一条容量是1的边;
* 把每个人和自己认识的人的床(如果有的话)之间连一条容量是1的边;
* 最后跑一遍Dinic再判断流量是否等于需要住宿的总人数即可。
*/

#include<bits/stdc++.h>
using namespace std;
#define Standard_Type long long
#define Content_Type long long
#define setEmpty(q) while(!q.empty())q.pop()
#define FILL(a,b) memset(a,b,sizeof a)
#define INF 2147483647
#define MAXM 200001
#define Queue_Standard_Type queue<Standard_Type>

/*Start : Struct declaration*/
struct __EDGE{
    Standard_Type from,to,next;
    Content_Type w;
    __EDGE(){
        from=0;
        to=0;
        next=0;
        w=0;
    }
};
/*End : Struct declaration*/

/*Start : Variable declaration*/
__EDGE edge[MAXM];
Standard_Type edgeHead[MAXM]={-1},edgeCount=-1,flag[MAXM],S,V;
Standard_Type n;
vector<Standard_Type> va,vb;
bool vis[100];
/*End : Variable declaration*/

/*Start : Function declaration*/
void INIT(); 
void Add(Standard_Type,Standard_Type,Content_Type);

bool BFS();

Content_Type DFS(Standard_Type,Content_Type);
Content_Type Dinic();

/*End : Function declaration*/

int main(){
    scanf("%lld",&n);
    while(~scanf("%lld",&n)){
        S=0;
        V=n+n+1;
        INIT();
        int x,tot=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            vis[i]=x;
            if(!x)tot++;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(vis[i]){
                Add(i+n,V,1);
                Add(V,i+n,0);
                if(!x){
                    tot++;
                    Add(S,i,1);
                    Add(i,S,0);
                    Add(i,i+n,1);
                    Add(i+n,i,0);
                }
            }else{
                Add(S,i,1);
                Add(i,S,0);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&x);
                if(x&&vis[j]){
                    Add(i,j+n,1);
                    Add(j+n,i,0);
                    Add(j,i+n,1);
                    Add(i+n,j,0);
                }
            }
        }
        if(Dinic()>=tot)puts("^_^");
        else puts("T_T");
    }
    return 0;
}

/*Start : Define*/
void INIT(){
    FILL(edgeHead,-1);
    FILL(vis,0);
}
void Add(Standard_Type from,Standard_Type to,Content_Type w){
    edge[++edgeCount].from=from;
    edge[edgeCount].to=to;
    edge[edgeCount].w=w;
    edge[edgeCount].next=edgeHead[from];
    edgeHead[from]=edgeCount;
}
bool BFS(){
    Standard_Type from,to;
    Queue_Standard_Type Queue;
    FILL(flag,-1);
    setEmpty(Queue);
    flag[S]=0;
    Queue.push(S);
    while(!Queue.empty()){
        from=Queue.front();
        Queue.pop();
        for(Standard_Type i=edgeHead[from];i!=-1;i=edge[i].next){
            to=edge[i].to;
            if(edge[i].w!=0&&flag[to]==-1){
                Queue.push(to);
                flag[to]=flag[from];
                flag[to]++;
            }
        }
    }
    if(flag[V]!=-1)return true;
    return false;
}
Content_Type DFS(Standard_Type from,Content_Type flow){
    if(from==V)return flow;
    Content_Type result=flow,minW;
    for(Standard_Type i=edgeHead[from];i!=-1;i=edge[i].next){
        if(result<=0)return flow-result;
        if(edge[i].w!=0&&flag[from]==flag[edge[i].to]-1){
            minW=DFS(edge[i].to,min(result,edge[i].w));
            edge[i^1].w+=minW;
            edge[i].w-=minW;
            result-=minW;
        }
    }
    return flow-result;
}
Content_Type Dinic(){
    Content_Type result=0;
    while(BFS()){
        result+=DFS(S,INF);
    }
    return result;
}
/*End : Define*/

附:样例的图

上图最大流是2,等于需要住宿的人数,所以答案是^_^

本来按照我的建图思路,P2和B1之间还有一条单向边。但鉴于P2未和源点连接,也就没画。