POJ

题目描述:

　　正如你所知道的，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= 110;//最大顶点数
const int MAXM = 11000;//最大边数
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=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int c){
    edges[tot].to=v;
    edges[tot].cap=c;
    edges[tot].flow=0;
    edges[tot].next=head[u];
    head[u]=tot++;
    edges[tot].to=u;
    edges[tot].cap=0;
    edges[tot].flow=0;
    edges[tot].next=head[v];
    head[v]=tot++;
}
void bfs(){
    memset(d,-1,sizeof(d));
    memset(gap,0,sizeof(gap));
    gap[0]=1;
    int front=0,rear=0;
    d[t]=0;
    que[rear++]=t;
    while(front!=rear){
        int u=que[front++];
        for(int i=head[u];i!=-1;i=edges[i].next){
            int v=edges[i].to;
            if(d[v]!=-1) continue;
            que[rear++]=v;
            d[v]=d[u]+1;
            gap[d[v]]++;
        }
    }
}
int isap(){
    bfs();
    memcpy(cur,head,sizeof(head));
    int top=0,x=s,flow=0;
    while(d[s]<N){
        if(x==t){
            int Min=INF,inser;
            for(int i=0;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=0;i<top;++i){
                edges[p[i]].flow+=Min;
                edges[p[i]^1].flow-=Min;
            }
            flow+=Min;
            top=inser;
            x=edges[p[top]^1].to;
            continue;
        }
        int ok=0;
        for(int i=cur[x];i!=-1;i=edges[i].next){
            int v=edges[i].to;
            if(edges[i].cap>edges[i].flow&&d[v]+1==d[x]){
                ok=1;
                cur[x]=i;
                p[top++]=i;
                x=edges[i].to;
                break;
            }
        }
        if(!ok){
            int Min=N;
            for(int i=head[x];i!=-1;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]]==0) break;
            gap[d[x]=Min+1]++;
            if(x!=s) x=edges[p[--top]^1].to;
        }
    }
    return flow;
}
int P;
struct Node{
    int p[15];
    int Q;
}node[MAXN];
bool check_edge(int i,int j){
    for(int k=0;k<P;++k){
        if(node[j].p[k]+node[i].p[k]==1) return false;//0-1搭配时
    }
    return true;
}
bool check_s(int i){
    for(int k=0;k<P;++k){
        if(node[i].p[k]==1) return false;
    }
    return true;
}
bool check_t(int i){
    for(int k=0;k<P;++k){
        if(node[i].p[k]==0) return false;
    }
    return true;
}
void Build_graph(){//建图
    s=0,t=(n<<1)+1;
    N=t+1;
    for(int i=1;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=1;i<=n;++i){
        for(int j=1;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=0;
    pi.clear();
    //在残量网络中查找流大于0的边
    for(int u=n+1;u<=(n<<1);++u){//生产点标号
        for(int i=head[u];i!=-1;i=edges[i].next){
            Edge&e =edges[i];
            int v=e.to;
            if(v!=u-n&&v!=t&&e.flow>0){
                cnt++;
                pi.push_back(make_pair(u-n,make_pair(v,e.flow)));
            }
        }
    }
    printf(" %d
",cnt);
    for(int i=0;i<cnt;++i){
        printf("%d %d %d
",pi[i].first,pi[i].second.first,pi[i].second.second);
    }
}
int main(){
    while(scanf("%d%d",&P,&n)!=EOF){
        init();
        for(int i=1;i<=n;++i){
            scanf("%d",&node[i].Q);
            for(int j=0;j<P;++j){
                scanf("%d",&node[i].p[j]);//接收点
            }
            for(int j=0;j<P;++j){
                scanf("%d",&node[i+n].p[j]);//生产点
            }
        }
        solve();
    }
    return 0;
}