题目连接：http://poj.org/submit?problem_id=3281
有人所用邻接矩阵会超时。。。然后。。。哥笑了~(*^__^*) 嘻嘻……
其实这题我觉得这不超时
这题一开始崔老师说把牛放中间我的意思是把人放在最前面，因为如果放在中间1头牛3物三水的话答案就会错误，但是如果把人放在前面感觉又会不大对= =。。然后崔老师就神一般的回答说拆点！顿时天亮了= =。。。其实我真心不知道拆点是神马。。。比赛有一道拆点我枚举匹配一下就过了。。虽然也是拆点的思想= =。。。
总之拆点就是为了先吃每个点的出度唯一（个人理解）而做的重复两次操作。博客的上一个acm computer其实就是拆点。。。但是没人点出来。。。还是崔老师是文化人毕竟出去学习过啊。。。在此给崔神跪了~。。。
代码
View Code
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <queue> 5 #define maxn 100000 6 using namespace std; 7 struct node 8 { 9 int fod[105],drk[105],f,d; 10 }cow[105]; 11 int cap[405][405]; 12 int ek(int n) 13 { 14 int f = 0,i; 15 int flow[405][405] = {0}; 16 memset(flow,0,sizeof(flow)); 17 int temp[405],pre[405]; 18 memset(pre,0,sizeof(pre)); 19 20 queue<int>q; 21 for(;;) 22 { 23 q.push(0); 24 memset(temp,0,sizeof(temp)); 25 temp[0] = maxn; 26 q.push(0); 27 while(!q.empty()) 28 { 29 int u = q.front(); 30 q.pop(); 31 for(i = 0; i <= n;i++) 32 { 33 if(!temp[i] && cap[u][i]>flow[u][i]) 34 { 35 q.push(i); 36 pre[i]= u; 37 temp[i] = min(temp[u],cap[u][i]-flow[u][i]); 38 } 39 } 40 } 41 if(temp[n] == 0) 42 break; 43 44 for(i = n;i != 0;i = pre[i]) 45 { 46 flow[pre[i]][i] += temp[n]; 47 flow[i][pre[i]] -= temp[n]; 48 } 49 f += temp[n]; 50 //printf("%d****\n",temp[n]); 51 } 52 return f; 53 } 54 int main() 55 { 56 int m,n,t,i,j,k; 57 int u; 58 int val; 59 while(~scanf("%d %d %d",&m,&n,&t)) 60 { 61 memset(cap,0,sizeof(cap)); 62 for(i = 1;i <= m;i++) 63 { 64 scanf("%d %d",&cow[i].f,&cow[i].d); 65 for(j = 1;j <= cow[i].f;j++) 66 { 67 68 scanf("%d",&val); 69 cap[val][n+i] = 1; 70 } 71 for(j = 1;j <= cow[i].d;j++) 72 { 73 scanf("%d",&val); 74 cap[n+m+i][n+m+m+val] = 1; 75 } 76 } 77 for(i = 1;i <= m;i++) 78 cap[n+i][n+m+i] = 1; 79 for(i = 1;i <= n;i++) 80 cap[0][i] = 1; 81 for(i = 1;i <= t;i++) 82 cap[n+m+m+i][n+2*m+t+1] = 1; 83 int res = ek(2*m+t+n+1); 84 cout<<res<<endl; 85 } 86 return 0; 87 }