【最大流】POJ3236-ACM Computer Factory

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<vector>
  8 #include<cmath>
  9 #include<queue>
 10 using namespace std;
 11 struct node 
 12 {
 13     int to,pos,cap;
 14 };
 15 const int MAXN=55;
 16 const int MAXP=15;
 17 const int MAXM=130;
 18 const int INF=0x7fffffff;
 19 int n,p;
 20 int s[MAXN][MAXP],q[MAXN][MAXP],value[MAXN];
 21 int vis[MAXM];
 22 vector<node> E[MAXM*MAXM];
 23 int dis[MAXM];
 24 int flow;
 25 
 26 void addedge(int u,int v,int w) 
 27 {
 28     /*
 29     POJ必须写成如下形式才能A，否则会CE 
 30     node tmp;
 31     tmp.to=v;
 32     tmp.pos=E[v].size();
 33     tmp.cap=w;
 34     E[u].push_back(tmp);
 35     tmp.to=u;
 36     tmp.pos=E[u].size()-1;
 37     tmp.cap=0;
 38     E[v].push_back(tmp);
 39     */
 40     E[u].push_back((node){v,E[v].size(),w});
 41     E[v].push_back((node){u,E[u].size()-1,0});
 42 }
 43 
 44 void init() 
 45 {
 46     scanf("%d%d",&p,&n) ;
 47     for (int i=0; i<n; i++) 
 48     {
 49         scanf("%d",&value[i]);
 50         for (int j=0; j<p; j++) 
 51             scanf("%d",&s[i][j]);
 52         for (int j=0; j<p; j++) 
 53             scanf("%d",&q[i][j]);
 54     }
 55 }
 56 
 57 void buildup() 
 58 {
 59     /*拆点*/
 60     for (int i=0; i<n; i++)
 61         addedge(i*2+1,i*2+2,value[i]);
 62 
 63     /*如果流入全为0或2，则与源点相连*/
 64     for (int i=0; i<n; i++) 
 65     {
 66         int flag=1;
 67         for (int j=0; j<p; j++) if (s[i][j]==1) 
 68         {
 69                 flag=0;
 70                 break;
 71         }
 72         if (flag) addedge(0,i*2+1,INF);
 73     }
 74 
 75     /*如果流出全为1或2，则与汇点相连*/
 76     for (int i=0; i<n; i++) 
 77     {
 78         int flag=1;
 79         for (int j=0; j<p; j++) if (q[i][j]==0)
 80         {
 81                 flag=0;
 82                 break;
 83         }
 84         if (flag) addedge(i*2+2,n*2+1,INF);
 85     }
 86 
 87     /*连边*/
 88     for (int i=0; i<n; i++)
 89         for (int j=0; j<n; j++) 
 90         {
 91             int flag=1;
 92             for (int k=0; k<p; k++)
 93                 if ((q[i][k]==1 && s[j][k]==0) || (q[i][k]==0 && s[j][k]==1)) 
 94                 {
 95                     flag=0;
 96                     break;
 97                 }
 98             if (flag) addedge(i*2+2,j*2+1,INF);
 99         }
100 }
101 
102 int bfs() 
103 {
104     memset(dis,-1,sizeof(dis));
105     queue<int> que;
106     que.push(0);
107     dis[0]=0;
108 
109     while (!que.empty()) 
110     {
111         int head=que.front();
112         que.pop();
113         for (int i=0; i<E[head].size(); i++) 
114         {
115             node tmp=E[head][i];
116             if (dis[tmp.to]!=-1 || tmp.cap<=0) continue;
117             dis[tmp.to]=dis[head]+1;
118             que.push(tmp.to);
119         }
120     }
121     if (dis[2*n+1]==-1) return 0;
122     else return 1;
123 }
124 
125 int dfs(int s,int e,int f) 
126 {
127     if (s==e) return(f);
128     vis[s]=1;/*不要遗漏这句语句*/
129     for (int i=0; i<E[s].size(); i++) 
130     {
131         node &tmp=E[s][i];
132         if (!vis[tmp.to] && dis[tmp.to]==dis[s]+1 && tmp.cap>0) 
133         {
134             int delta=dfs(tmp.to,e,min(tmp.cap,f));
135             if (delta>0) 
136             {
137                 tmp.cap-=delta;
138                 E[tmp.to][tmp.pos].cap+=delta;
139                 return delta;
140             }
141         }
142     }
143     return 0;
144 }
145 
146 void Dinic() 
147 {
148     flow=0;
149     while (bfs()) 
150     {
151         for (;;) 
152         {
153             memset(vis,0,sizeof(vis));
154             int f=dfs(0,2*n+1,INF);
155             if (f==0) break;
156             else flow+=f;
157         }
158     }
159 }
160 
161 void output() 
162 {
163     cout<<flow<<‘ ‘;
164     int M=0,l[MAXN],r[MAXN],c[MAXN];
165     for (int i=1; i<2*n+1; i++)
166         for (int j=0; j<E[i].size(); j++) 
167         {
168             node tmp=E[i][j];
169             if (E[tmp.to][tmp.pos].cap>0 && E[tmp.to][tmp.pos].cap<=flow && tmp.to!=2*n+1 && ((tmp.to+1)>>1!=(i+1)>>1)) 
170             {
171                 M++;
172                 l[M]=(i+1)>>1;
173                 r[M]=(tmp.to+1)>>1;
174                 c[M]=E[tmp.to][tmp.pos].cap;
175             }
176         }
177     cout<<M<<endl;
178     for (int i=1; i<=M; i++) cout<<l[i]<<‘ ‘<<r[i]<<‘ ‘<<c[i]<<endl;
179 }
180 
181 int main()
182 {
183         init();
184         buildup();
185         Dinic();
186         output();
187         return 0;
188 }