1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 3309  Solved: 1395

[][][]

Description

Input

Output

Sample Input

1

3

1 1 0

0 1 0

0 1 1

1 0 0

1 0 0

Sample Output

^_^

HINT

对于30% 的数据满足1 ≤ n ≤ 12。

对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

Source

每个有床位的同学把他的床向汇点连边，需要床的由源点向他连边，a认识b将a向b的床连边；然后跑最大流；貌似这个问题挺经典的？？？ laj还需继续努力qwq

 

1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=305; 5 int T,n,m,s,t,a[MAX],tx,ans; 6 int tot,head[MAX],adj[MAX*MAX],wei[MAX*MAX],next[MAX*MAX]; 7 int deep[MAX],cur[MAX]; 8 void addedge(int u,int v,int w){ 9     tot++;adj[tot]=v,wei[tot]=w,next[tot]=head[u],head[u]=tot;10 }11 bool bfs(){12     int i,j,u;13     memset(deep,127,sizeof(deep));14     deep[s]=0;15     queue 
     
       q;q.push(s);16     while (!q.empty()){17         u=q.front();q.pop();18         for (i=head[u];i;i=next[i]){19             if (deep[adj[i]]>1e9 && wei[i]>0){20                 deep[adj[i]]=deep[u]+1;21                 q.push(adj[i]);22             }23         }24     }25     return deep[t]<1e9;26 }27 int dfs(int x,int flo){28     if (flo==0 || x==t) return flo;29     int j;30     for (int &i=cur[x];i;i=next[i]){31         if (deep[adj[i]]==deep[x]+1 && wei[i]>0){32             j=dfs(adj[i],min(flo,wei[i]));33             if (j) return wei[i]-=j,wei[i^1]+=j,j;34         }35     }36     return 0;37 }38 int main(){39     freopen ("document.in","r",stdin);freopen ("document.out","w",stdout);40     int i,j,zt;41     scanf("%d",&T);42     while (T--){43         tot=1,memset(head,0,sizeof(head));tx=0;44         scanf("%d",&n);s=2*n+1,t=2*n+2;45         for (i=1;i<=n;i++){46             scanf("%d",a+i);47             if (a[i]==1) addedge(i+n,t,1),addedge(t,i+n,0);48         }49         for (i=1;i<=n;i++){50             scanf("%d",&zt);51             if (!a[i] || (a[i] && !zt))52                 addedge(s,i,1),addedge(i,s,0),tx++;53         }54         for (i=1;i<=n;i++){55             for (j=1;j<=n;j++){56                 scanf("%d",&zt);57                 if ((i==j) || zt==1)58                     addedge(i,j+n,1),addedge(j+n,i,0);59             }60         }ans=0;int dd;61         while (bfs()){62             for (i=1;i<=2*n+2;i++) cur[i]=head[i];63             while (dd=dfs(s,1e9)) ans+=dd;64         }65         if (ans==tx) puts("^_^");66         else puts("T_T");67     }68     return 0;69 }