https://vjudge.net/problem/POJ-3436
题目描述:
正如你所知道的，ACM 竞赛中所有竞赛队伍使用的计算机必须是相同的，以保证参赛者在公平的环境下竞争。这就是所有这些计算机都是同一个厂家生产的原因。 每台ACM 计算机包含P 个部件，当所有这些部件都准备齐全后，计算机就可以组装了，组装好以后就可以交给竞赛队伍使用了。计算机的生产过程是全自动的，通过N 台不同的机器来完成。每台机器从一台半成品计算机中去掉一些部件，并加入一些新的部件（去除一些部件在有的时候是必须的，因为计算机的部件不能以任意的顺序组装）。每台机器用它的性（每小时组装多少台计算机）、输入/输出规格来描述。
输入规格描述了机器在组装计算机时哪些部件必须准备好了。输入规格是由P 个整数组成， 每个整数代表一个部件，这些整数取值为0, 1 或2，其中0 表示该部件不应该已经准备好了，1表示该部件必须已经准备好了，2 表示该部件是否已经准备好了无关紧要。
输出规格描述了该机器组装的结果。输出规格也是由P 个整数组成，每个整数取值为0 或1，其中0 代表该部件没有生产好，1 代表该部件生产好了。 机器之间用传输速度非常快的流水线连接，部件在机器之间传送所需的时间与机器生产时间相比是十分小的。
经过多年的运转后，ACM 计算机工厂的整体性能已经远远不能满足日益增长的竞赛需求。因此ACM 董事会决定升级工厂。升级工厂最好的方法是重新调整流水线。ACM 董事会决定让你来解决这个问题。
求大最流，然后输出机器之间流量增加的边
思路：
网络流模型：
1) 添加一个原点S,S提供最初的原料 00000...
2) 添加一个汇点T, T接受最终的产品 11111...
3) 将每个机器拆成两个点: 编号为i的接收节点，和编号为i+n的产出节点（n是机器数目），前者用于接收原料，后者用于提供加工后的半成品或成品。这两个点之间要连一条边，容量为单位时间产量Qi
4) S 连边到所有接收 "0000..." 或 "若干个0及若干个2" 的机器，容量为无穷大
5) 产出节点连边到能接受其产品的接收节点，容量无穷大
6) 能产出成品的节点，连边到T，容量无穷大。
7) 求S到T的最大流
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
const int MAXN= ;//最大顶点数
const int MAXM = ;//最大边数
const int INF=0x3f3f3f3f;
using namespace std;
vector<pair<int,pair<int,int> > >pi;
int n,s,t,N;
struct Edge{
int to,next,cap,flow;
}edges[MAXM];
int head[MAXN],tot,gap[MAXN],d[MAXN],cur[MAXN],que[MAXN],p[MAXN];
void init(){
tot=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int c){
edges[tot].to=v;
edges[tot].cap=c;
edges[tot].flow=;
edges[tot].next=head[u];
head[u]=tot++;
edges[tot].to=u;
edges[tot].cap=;
edges[tot].flow=;
edges[tot].next=head[v];
head[v]=tot++;
}
void bfs(){
memset(d,-,sizeof(d));
memset(gap,,sizeof(gap));
gap[]=;
int front=,rear=;
d[t]=;
que[rear++]=t;
while(front!=rear){
int u=que[front++];
for(int i=head[u];i!=-;i=edges[i].next){
int v=edges[i].to;
if(d[v]!=-) continue;
que[rear++]=v;
d[v]=d[u]+;
gap[d[v]]++;
}
}
}
int isap(){
bfs();
memcpy(cur,head,sizeof(head));
int top=,x=s,flow=;
while(d[s]<N){
if(x==t){
int Min=INF,inser;
for(int i=;i<top;++i){
if(Min>edges[p[i]].cap-edges[p[i]].flow){
Min=edges[p[i]].cap-edges[p[i]].flow;
inser=i;
}
}
for(int i=;i<top;++i){
edges[p[i]].flow+=Min;
edges[p[i]^].flow-=Min;
}
flow+=Min;
top=inser;
x=edges[p[top]^].to;
continue;
}
int ok=;
for(int i=cur[x];i!=-;i=edges[i].next){
int v=edges[i].to;
if(edges[i].cap>edges[i].flow&&d[v]+==d[x]){
ok=;
cur[x]=i;
p[top++]=i;
x=edges[i].to;
break;
}
}
if(!ok){
int Min=N;
for(int i=head[x];i!=-;i=edges[i].next){
if(edges[i].cap>edges[i].flow&&d[edges[i].to]<Min){
Min=d[edges[i].to];
cur[x]=i;
}
}
if(--gap[d[x]]==) break;
gap[d[x]=Min+]++;
if(x!=s) x=edges[p[--top]^].to;
}
}
return flow;
}
int P;
struct Node{
int p[];
int Q;
}node[MAXN];
bool check_edge(int i,int j){
for(int k=;k<P;++k){
if(node[j].p[k]+node[i].p[k]==) return false;//0-1搭配时
}
return true;
}
bool check_s(int i){
for(int k=;k<P;++k){
if(node[i].p[k]==) return false;
}
return true;
}
bool check_t(int i){
for(int k=;k<P;++k){
if(node[i].p[k]==) return false;
}
return true;
}
void Build_graph(){//建图
s=,t=(n<<)+;
N=t+;
for(int i=;i<=n;++i){
if(check_s(i)) addedge(s,i,INF);//和只有0，2的接收点连接
addedge(i,i+n,node[i].Q);//接收点和生产点间容量为处理率
if(check_t(i+n)) addedge(i+n,t,INF);//和全1的生产点连接
}
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
if(j==i) continue;
if(check_edge(i+n,j)) addedge(i+n,j,INF);//生产点和接收点的连接
}
}
}
void solve(){
Build_graph();
printf("%d",isap());
//输出关系
int cnt=;
pi.clear();
//在残量网络中查找流大于0的边
for(int u=n+;u<=(n<<);++u){//生产点标号
for(int i=head[u];i!=-;i=edges[i].next){
Edge&e =edges[i];
int v=e.to;
if(v!=u-n&&v!=t&&e.flow>){
cnt++;
pi.push_back(make_pair(u-n,make_pair(v,e.flow)));
}
}
}
printf(" %d\n",cnt);
for(int i=;i<cnt;++i){
printf("%d %d %d\n",pi[i].first,pi[i].second.first,pi[i].second.second);
}
}
int main(){
while(scanf("%d%d",&P,&n)!=EOF){
init();
for(int i=;i<=n;++i){
scanf("%d",&node[i].Q);
for(int j=;j<P;++j){
scanf("%d",&node[i].p[j]);//接收点
}
for(int j=;j<P;++j){
scanf("%d",&node[i+n].p[j]);//生产点
}
}
solve();
}
return ;
}