【BZOJ 1433】 [ZJOI2009]假期的宿舍

1433: [ZJOI2009]假期的宿舍Time Limit:10 SecMemory Limit:162 MBSubmit:1318Solved:575[Submit][Status]Description

Input

Output

Sample Input

131 1 00 1 00 1 11 0 01 0 0

Sample Output

HINT

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

二分图。

左部点外校的和不回家的本校学生，右部点为所有床。

学生能睡到哪个床上就连一条边。

求二分图最大匹配，，必须满足每一个都有匹配，否则就是无解。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cstdlib>#define M 100+5using namespace std;int h[M],tot,v[M],my[M],sc[M],go[M],a[M][M],T,n;struct edge{int y,ne;}e[20000+5];void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;}bool dfs(int x){for (int i=h[x];i;i=e[i].ne){int y=e[i].y;if (!v[y]){v[y]=1;if (!my[y]||dfs(my[y])){my[y]=x;return true;}}}return false;}int main(){read(T);while (T–){read(n);for (int i=1;i<=n*2;i++)h[i]=0,my[i]=0;tot=0;for (int i=1;i<=n;i++)read(sc[i]);for (int i=1;i<=n;i++){read(go[i]);if (sc[i]&&!go[i]) Addedge(i,n+i);}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++)read(a[i][j]);if (!sc[i]||(sc[i]&&!go[i])){for (int j=1;j<=n;j++)if (a[i][j]&&sc[j]) Addedge(i,j+n);}}int f=1;for (int i=1;i<=n;i++)if (!sc[i]||(sc[i]&&!go[i])){for (int j=1;j<=n*2;j++)v[j]=0;if (!dfs(i)) {f=0;break;}}if (f) puts("^_^");else puts("T_T");}return 0;}

感悟：

这道题0分了好多次，发现是连边的问题：

如果两个人认识，那么对方必须是本校学生才能和他对应的床连边。。

美不美乡中水，亲不亲故乡人。