poj3436ACM Computer Factory（最大流）

刚开始做的没拆点 BFS的时候保存了下路径恰好样例都过了接着就是各种WA
搜了搜解题报告是将一个电脑拆成2个点这两点之间限制容量电脑与电脑之间容量为INF 设置一个源点和汇点源点全是0 汇点全是1
不用保存路径在最后比较一下现在的容量和原始容量差值就为W
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define INF 0x3f3f3f
  8 int n,m;
  9 struct node
 10 {
 11     int s[15],d[15];
 12     int q;
 13 }ma[110];
 14 int path[110],flow[110],map[110][110],st,en,tmap[110][110];
 15 int bfs()
 16 {
 17     int i,j,k;
 18     memset(path,-1,sizeof(path));
 19     for(i = 0 ; i <= en ; i++)
 20     flow[i] = INF;
 21     queue<int>q;
 22     q.push(0);
 23     while(!q.empty())
 24     {
 25         int tk = q.front();
 26         q.pop();
 27         if(tk==en)
 28         break;
 29         for(i = 1 ; i <= en ; i++)
 30         {
 31             if(path[i]==-1&&map[tk][i])
 32             {
 33                 path[i] = tk;
 34                 flow[i] = min(flow[tk],map[tk][i]);
 35                 q.push(i);
 36             }
 37         }
 38     }
 39     if(path[en]==-1)
 40     return -1;
 41     return flow[en];
 42 }
 43 int karp()
 44 {
 45     int i,j,k,now,pre,sum=0;
 46     while((k=bfs())!=-1)
 47     {
 48         sum+=k;
 49         now = en;
 50         while(now!=st)
 51         {
 52             pre = path[now];
 53             map[pre][now]-=k;
 54             map[now][pre]+=k;
 55             now = pre;
 56         }
 57     }
 58     return sum;
 59 }
 60 int main()
 61 {
 62     int i,j,k,g;
 63     while(cin>>n>>m)
 64     {
 65         memset(map,0,sizeof(map));
 66         memset(tmap,0,sizeof(tmap));
 67         for(i = 1; i <= m ; i++)
 68         {
 69             cin>>ma[i].q;
 70             for(j = 1 ; j <= n ; j++)
 71             cin>>ma[i].s[j];
 72             for(j = 1; j <= n; j++)
 73             cin>>ma[i].d[j];
 74             map[i][i+m] = ma[i].q;
 75             tmap[i][i+m] = ma[i].q;
 76         }
 77         for(i = 1; i <= m ; i++)
 78         {
 79             int f = 1;
 80             for(j = 1; j <= n ; j++)
 81             if(ma[i].s[j]==1)
 82             {
 83                 f = 0;
 84                 break;
 85             }
 86             if(f)
 87             {
 88                 map[0][i] = INF;
 89                 tmap[0][i] = INF;
 90             }
 91         }
 92         for(i = 1; i <= m ; i++)
 93         {
 94             int f = 1;
 95             for(j = 1; j <= n ; j++)
 96             if(ma[i].d[j]!=1)
 97             {
 98                 f = 0;
 99                 break;
100             }
101             if(f)
102             {
103                 map[i+m][2*m+1] = INF;
104                 tmap[i+m][2*m+1] = INF;
105             }
106         }
107         for(i = 1; i <= m ; i++)
108         for(j = 1; j <= m ; j++)
109         {
110             int flag = 1;
111             if(i==j)
112             continue;
113             for(g = 1; g <= n ; g++)
114             {
115                 if(ma[j].s[g]==2)
116                 continue;
117                 if(ma[i].d[g]!=ma[j].s[g])
118                 {
119                     flag = 0;
120                     break;
121                 }
122             }
123             if(flag)
124             {
125                 map[i+m][j] = INF;
126                 tmap[i+m][j] = map[i+m][j];
127             }
128         }
129         en = 2*m+1;st = 0;
130         int num = 0;
131         int ss  = karp();
132         for(i = m+1; i < en ;i++)
133         for(j = 1 ; j <= m ; j++)
134         if(i!=j&&map[i][j]<tmap[i][j])
135         num++;
136         cout<<ss<<" "<<num<<endl;
137         for(i = m+1; i < en ;i++)
138         for(j = 1 ; j <= m ; j++)
139         if(i!=j&&map[i][j]<tmap[i][j])
140         {
141             cout<<i-m<<" "<<j<<" "<<tmap[i][j]-map[i][j]<<endl;
142         }
143     }
144     return 0;
145 }