POJ3436 ACM Computer Factory 最大流

　　题目噼里啪啦说了一大堆= =，其实很简单。对每个点拆点u-v，然后加限制容量，如果两个点之间可行，那么加边，容量INF，最后加源点s和汇点t，建立有向图后，求大流。只是这个题目的建图有点麻烦，果断用3进制优化后，内存减少了很多，处理上也方便了很多。
  1 //STATUS:C++_AC_0MS_180KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 using namespace std;
 13 #define LL __int64
 14 #define pii pair<int,int>
 15 #define Max(a,b) ((a)>(b)?(a):(b))
 16 #define Min(a,b) ((a)<(b)?(a):(b))
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define lson l,mid,rt<<1
 19 #define rson mid+1,r,rt<<1|1
 20 #define put1(i,j,num) (li[i][0]|=(num<<(j<<1)))
 21 #define get1(i,j) ((li[i][0]&(3<<(j<<1)))>>(j<<1))
 22 #define put2(i,j,num) (li[i][1]|=(num<<j))
 23 #define get2(i,j) ((li[i][1]&(1<<j))>>j)
 24 const int N=102,INF=0x3f3f3f3f,MOD=1999997;
 25 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
 26 
 27 struct Edge{
 28     int u,v,cap,flow;
 29 }e[N*N];
 30 
 31 int first[N],next[N*N],cur[N],d[N],w[51],li[51][2],num[N],p[N];
 32 int n,m,S,T,mt;
 33 
 34 void adde(int a,int b,int val)
 35 {
 36     e[mt].u=a,e[mt].v=b;
 37     e[mt].cap=val,e[mt].flow=0;
 38     next[mt]=first[a],first[a]=mt++;
 39     e[mt].u=b,e[mt].v=a;
 40     e[mt].cap=0,e[mt].flow=0;
 41     next[mt]=first[b],first[b]=mt++;
 42 }
 43 
 44 int ok(int a,int b)
 45 {
 46     int i;
 47     for(i=0;i<n;i++){
 48         if(get1(b,i)!=2 && get1(b,i)!=get2(a,i))
 49             return 0;
 50     }
 51     return 1;
 52 }
 53 
 54 void getg()
 55 {
 56     int i,j,flag;
 57     for(i=1;i<=m;i++)
 58         adde(i,i+m,w[i]);
 59     for(i=1;i<=m;i++)
 60         for(j=1;j<=m;j++)
 61             if(i!=j && ok(i,j))adde(i+m,j,INF);
 62         for(i=1;i<=m;i++){
 63             for(j=flag=0;j<n;j++)
 64                 if(get1(i,j)==1){flag=1;break;}
 65             if(!flag)adde(S,i,INF);
 66             if(li[i][1]==((1<<n)-1))adde(i+m,T,INF);
 67     }
 68 }
 69 
 70 int augment()
 71 {
 72     int i=T,a=INF;
 73     while(i!=S){
 74         a=Min(a,e[p[i]].cap-e[p[i]].flow);
 75         i=e[p[i]].u;
 76     }
 77     i=T;
 78     while(i!=S){
 79         e[p[i]].flow+=a;
 80         e[p[i]^1].flow-=a;
 81         i=e[p[i]].u;
 82     }
 83     return a;
 84 }
 85 
 86 int isap()
 87 {
 88     int x,i,min,flow=0,ok;
 89     mem(d,0);mem(num,0);
 90     num[0]=T+1;
 91     for(i=0;i<=T;i++)cur[i]=first[i];
 92     x=S;
 93     while(d[S]<=T)
 94     {
 95         if(x==T){
 96             flow+=augment();
 97             x=S;
 98         }
 99         ok=0;
100         for(i=cur[x];i!=-1;i=next[i]){
101             if(e[i].cap>e[i].flow && d[x]==d[e[i].v]+1){
102                 ok=1;
103                 p[e[i].v]=i;
104                 cur[x]=i;
105                 x=e[i].v;
106                 break;
107             }
108         }
109         if(!ok){
110             min=T;
111             for(i=first[x];i!=-1;i=next[i])
112                 if(e[i].cap>e[i].flow && d[e[i].v]<min)min=d[e[i].v];
113             if(--num[d[x]]==0)break;
114             num[d[x]=min+1]++;
115             cur[x]=first[x];
116             if(x!=S)x=e[p[x]].u;
117         }
118     }
119     return flow;
120 }
121 
122 int main()
123 {
124  //   freopen("in.txt","r",stdin);
125     int i,j,t;
126     int ans[N][3],cou;
127     while(~scanf("%d%d",&n,&m))
128     {
129         cou=mt=S=0;
130         T=2*m+1;
131         mem(li,0);
132         mem(first,-1);
133         for(i=1;i<=m;i++){
134             scanf("%d",&w[i]);
135             for(j=0;j<n;j++){
136                 scanf("%d",&t);
137                 put1(i,j,t);
138             }
139             for(j=0;j<n;j++){
140                 scanf("%d",&t);
141                 put2(i,j,t);
142             }
143         }
144 
145         getg();
146         printf("%d",isap());
147 
148         for(i=m;i<T;i++){
149             for(j=first[i];j!=-1;j=next[j]){
150                 if(e[j].v<=m && e[j].flow>0){
151                     ans[cou][0]=i-m;
152                     ans[cou][1]=e[j].v;
153                     ans[cou++][2]=e[j].flow;
154                 }
155             }
156         }
157         printf(" %d\n",cou);
158         for(i=0;i<cou;i++)
159             printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
160     }
161     return 0;
162 }