题解 P2055 【[ZJOI2009]假期的宿舍】
t162
2019-08-14 14:56:46
解题思路在代码中。
```cpp
/*
* 我的思路：遇到需要住宿的人就让他和源点之间连一条容量是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未和源点连接，也就没画。