[solution] the maximum flow problem of poj3436 ACM Computer Factory

First of all, each machine is divided into two points, connecting the edge with the capacity of vvv. Establish a super source sink. The start point of source connection is all 0, the capacity INF, the end point of sink connection is all 1, the capacity INF. if the start point and the end point are matched, connect the side with the capacity INF. Then run the maximum current from the source point, and the reverse arc capacity is obtained.
Implementation with adjacency matrix, code reference Big guy's solution

```#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int p,n,c[210][210],a[210][20],s,t,maxflow,d[210],pre[210],cnt,from[210],to[210],num[210];
bool bfs()
{
memset(d,0,sizeof(d));
queue<int>q;while(q.size())q.pop();q.push(s);d[s]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int v=s;v<=t;v++)
if(c[u][v]&&!d[v])
{
q.push(v);d[v]=d[u]+1;pre[v]=u;
if(v==t)return 1;
}
}
return 0;
}
int dinic(int u,int flow)
{
if(u==t)return flow;
int k=flow;
for(int v=t;v!=s;v=pre[v])
k=min(k,c[pre[v]][v]);
for(int v=t;v!=s;v=pre[v])
c[pre[v]][v]-=k,c[v][pre[v]]+=k;
return k;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&p,&n);s=0;t=2*n+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i][i+n]);
for(int j=1;j<=p;j++)
scanf("%d",&a[i][j]);
for(int j=1;j<=p;j++)
scanf("%d",&a[i+n][j]);
}
for(int i=1;i<=n;i++)
{
bool flag=1;
for(int j=1;j<=p;j++)
if(a[i][j]==1){flag=0;break;}
if(flag)c[0][i]=INF;
flag=1;
for(int j=1;j<=p;j++)
if(a[i+n][j]!=1){flag=0;break;}
if(flag)c[i+n][2*n+1]=INF;
}
for(int i=n+1;i<=2*n;i++)
for(int j=1;j<=n;j++)
{
bool flag=1;
for(int k=1;k<=p;k++)
if(a[i][k]+a[j][k]==1){flag=0;break;}//Mismatch
if(flag)c[i][j]=INF;
}
int flow=0;
while(bfs())while(flow=dinic(s,INF))maxflow+=flow;
printf("%d ",maxflow);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(c[j][i+n]&&i!=j)
cnt++,from[cnt]=i,to[cnt]=j,num[cnt]=c[j][i+n];
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d %d %d\n",from[i],to[i],num[i]);
return 0;
}
```

summary

A good problem to study modeling. The common method of breaking points is to solve the problem by building the map and running the maximum flow.

Added by groovything on Tue, 17 Dec 2019 19:25:58 +0200