ACM Computer Factory

ACM Computer Factory
网络流Dinic
将一个机器拆分成两个点，这两个点之间的容量为机器的加工量；建立一个超级源点和超级汇点，并将满足条件的点连接在一起，容量均为inf。之后跑Dinic算法即可。
注意输出的时候不要求输出为路径顺序（这里坑了一晚上才知道不需要=。=）
代码如下：
  1 #include <cstdio>
  2 #include <vector>
  3 #include <cstring>
  4 #include <queue>
  5 #define pb(x) push_back(x)
  6 #define N 200
  7 using namespace std;
  8 int const inf=1<<30;
  9 struct edge{
 10     int to,rev,cap;
 11     edge(int _to=0,int _cap=0,int _rev=0){
 12         to=_to;rev=_rev;cap=_cap;
 13     }
 14 };
 15 struct node{
 16     int from,to,c;
 17     node(int _from=0,int _to=0,int _c=0){
 18         from=_from;to=_to;c=_c;
 19     }
 20 };
 21 struct dinic{
 22     vector<edge>g[N];
 23     int level[N],iter[N];
 24     void init(int s,int t){
 25         for(int i=s;i<=t;++i)g[i].clear();
 26     }
 27     void add(int u,int v,int c){
 28         g[u].pb(edge(v,c,g[v].size()));
 29         g[v].pb(edge(u,0,g[u].size()-1));
 30     }
 31     bool bfs(int s,int t){
 32         memset(level,-1,sizeof(level));
 33         queue<int>q;
 34         q.push(s);
 35         level[s]=0;
 36         while(!q.empty()){
 37             int u=q.front();q.pop();
 38             for(int i=0;i<g[u].size();++i){
 39                 edge e=g[u][i];
 40                 if(level[e.to]<0&&e.cap>0){
 41                     level[e.to]=level[u]+1;
 42                     q.push(e.to);
 43                 }
 44             }
 45         }
 46         return level[t]>=0;
 47     }
 48     int dfs(int u,int t,int f){
 49         if(u==t)return f;
 50         for(int &i=iter[u];i<g[u].size();++i){
 51             edge &e=g[u][i];
 52             if(level[u]<level[e.to]&&e.cap>0){
 53                 int d=dfs(e.to,t,f>e.cap?e.cap:f);
 54                 if(d>0){
 55                     e.cap-=d;
 56                     g[e.to][e.rev].cap+=d;
 57                     return d;
 58                 }
 59             }
 60         }
 61         return 0;
 62     }
 63     int maxflow(int s,int t){
 64         int flow=0,f;
 65         while(bfs(s,t)){
 66             memset(iter,0,sizeof(iter));
 67             while((f=dfs(s,t,inf))>0)flow+=f;
 68         }
 69         return flow;
 70     }
 71     void print(int n){
 72         printf("%d ",maxflow(0,1));
 73         int ans=0;
 74         for(int i=1;i<=2*n;++i){
 75             for(int j=0;j<g[2*i+1].size();++j){
 76                 edge e=g[2*i+1][j];
 77                 if(e.to!=1&&e.cap>0&&e.cap<inf&&e.to!=2*i)
 78                     ans++;
 79             }
 80         }
 81         printf("%d
",ans);
 82         for(int i=1;i<=2*n;++i){
 83             for(int j=0;j<g[2*i+1].size();++j){
 84                 edge e=g[2*i+1][j];
 85                 if(e.to!=1&&e.cap>0&&e.cap<inf&&e.to!=2*i)
 86                     printf("%d %d %d
",i,e.to/2,inf-e.cap);
 87             }
 88         }
 89     }
 90 }G;
 91 int p,n;
 92 struct nod{
 93     int c,in[15],out[15];
 94     void add(){
 95         scanf("%d",&c);
 96         for(int i=0;i<p;++i)
 97             scanf("%d",&in[i]);
 98         for(int i=0;i<p;++i)
 99             scanf("%d",&out[i]);
100     }
101     bool match(nod t){
102         for(int i=0;i<p;++i)
103             if(out[i]+t.in[i]==1)return 0;
104         return 1;
105     }
106     bool ifs(){
107         for(int i=0;i<p;++i)
108             if(in[i]==1)return 0;
109         return 1;
110     }
111     bool ift(){
112         for(int i=0;i<p;++i)
113             if(out[i]==0)return 0;
114         return 1;
115     }
116 }a[55];
117 void init(){
118     G.init(0,2*n+2);
119     for(int i=1;i<=n;++i){
120         a[i].add();//s=0,t=1
121         G.add(2*i,2*i+1,a[i].c);//将i拆成2*i和2*i+1
122         if(a[i].ifs())G.add(0,2*i,inf);
123         if(a[i].ift())G.add(2*i+1,1,inf);
124     }
125     for(int i=1;i<=n;++i)
126     for(int j=1;j<=n;++j)
127     if(i!=j&&a[i].match(a[j]))
128         G.add(2*i+1,2*j,inf);
129 }
130 int main(void){
131     while(~scanf("%d%d",&p,&n)){
132         init();
133         G.print(n);
134     }
135 }