假期的宿舍
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1433
二分图匹配（最大流）
做到Candy（http://acm.split.hdu.edu.cn/showproblem.php?pid=4322）这道题，用A*写了半天TLE了，去网上搜题解，都是网络流的做法。问艾神用搜索做该怎么剪枝，艾神说他写的书上有讲很多剪枝策略，然而最快三天后书才能到....，所以就先试试网络流了。 之前没怎么接触过网络流，看了半天才看懂一些，于是就拿这题入门了。
这题是二分图匹配的入门题，将留校的同学和看望的同学作为一个点集，将本校生（床）作为另一个点集，并根据关系矩阵进行连接。（init的时候没把vector清了，简直智障...）
代码如下：
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<iostream> 5 #define met(a,b) memset(a,b,sizeof(a)); 6 #define N 55 7 using namespace std; 8 int match[2*N]; 9 bool used[2*N]; 10 int home[N]; 11 int bed[N]; 12 int mp[N][N]; 13 vector<int>e[2*N]; 14 int T,n,sum,person; 15 void init(){ 16 sum=0,person=0; 17 met(match,-1); 18 for(int i=0;i<2*N;++i) 19 e[i].clear(); 20 } 21 bool dfs(int v){ 22 used[v]=1; 23 for(vector<int>::size_type i=0;i<e[v].size();++i){ 24 int u=e[v][i],w=match[u]; 25 if(w<0||(!used[w]&&dfs(w))){//如果u没被匹配 或者 u已经被w匹配，但w可以找到其他匹配 26 match[v]=u; 27 match[u]=v; 28 return 1; 29 } 30 } 31 return 0; 32 } 33 int main(void){ 34 scanf("%d",&T); 35 while(T--){ 36 init(); 37 /*----读取----*/ 38 scanf("%d",&n); 39 for(int i=0;i<n;++i)//1有床 0没床 40 scanf("%d",&bed[i]); 41 for(int i=0;i<n;++i)//1回家 0不回家 42 scanf("%d",&home[i]); 43 for(int i=0;i<n;++i) 44 for(int j=0;j<n;++j)//关系矩阵 45 scanf("%d",&mp[i][j]); 46 /*----建图----*/ 47 for(int i=0;i<n;++i) 48 if(home[i]==0||bed[i]==0){//不回家或者没有床 49 person++; 50 for(int j=0;j<n;++j) 51 if(bed[j]==1&&(mp[i][j]==1||i==j)){//j有床并且i可以睡j的床 52 e[i].push_back(j+n); 53 e[j+n].push_back(i); 54 } 55 } 56 /*----最大匹配----*/ 57 for(int i=0;i<2*n;++i) 58 if(match[i]<0){ 59 met(used,0); 60 if(dfs(i)) 61 sum++; 62 } 63 if(sum==person)printf("%c%c%c ",94,95,94); 64 else printf("%c%c%c ",84,95,84); 65 } 66 }