http://poj.org/problem?id=3436
每台电脑有$p$个组成部分，有$n$个工厂加工电脑。
每个工厂对于进入工厂的半成品的每个组成部分都有要求，由$p$个数字描述，0代表这个部分不能有，1代表这个部分必须有，2代表这个部分的有无无所谓。
每个工厂的产出也不尽相同，也是由p个数字代表，0代表这个部分不存在，1代表这个部分存在。每个工厂都有一个最大加工量。
给出这$n$个工厂的数据，求出最多能加工出多少台电脑
对于容量有限制,因此拆点
开始的机器没有零件,连接符合要求的点
最终的机器应该是完整的,把符合要求的点连接到汇点
因为已经拆过点限制了流量,所以其余容量记为INF就行了,
关于路径还原 在链式前向星保存边的时候同时记录边的起点,最后反向弧非零的边就是答案
#include <string.h> #include <algorithm> #include <stdio.h> #include <vector> #include <iostream> #define ll long long #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pp pair<int,int> #define rep(ii,a,b) for(int ii=a;ii<=b;ii++) #define per(ii,a,b) for(int ii=a;ii>=b;ii--) #define show(x) cout<<#x<<"="<<x<<endl #define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl #define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl #define showa(a,b) cout<<#a<<'['<<b<<"]="<<b[a]<<endl using namespace std; const int maxn=123+10;
const int maxm=1234+10; const int INF=0x3f3f3f3f; int casn,n,m,k; struct node {int pre,to,cap,next;}e[maxm]; int ss,tt,head[maxn],nume,dis[maxn]; inline void addx(int a,int b,int c){ e[++nume]=(node){a,b,c,head[a]}; head[a]=nume; } inline void add(int a,int b,int c){ addx(a,b,c);addx(b,a,0); } bool bfs(int s=ss,int t=tt){ int top=0,end=1; int q[maxn]; q[0]=s; // for(int i=0;i<=t;i++) dis[i]=0; memset(dis,0,sizeof dis); dis[s]=1; while(top!=end){ int now=q[top++];top%=maxn; for(int i=head[now];i;i=e[i].next){ int to=e[i].to; if(!dis[to]&&e[i].cap){ dis[to]=dis[now]+1; if(to==t)break; q[end++]=to;end%=maxn; } } } return dis[t]; } int dfs(int now=ss,int last=INF){ if(now==tt)return last; int flow=0,det; for(int i=head[now];i;i=e[i].next){ int to=e[i].to; if(e[i].cap&&dis[to]==dis[now]+1){ det=dfs(to,min(last-flow,e[i].cap)); flow+=det; e[i].cap-=det; e[i^1].cap+=det; if(flow==last) return last; } } dis[now]=-1; return flow; } int p; int cost[123]; int in[123][12]; int out[123][12]; int a[123]; int main(){ //#define test #ifdef test freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #endif nume=1; IO; cin>>p>>n; ss=0,tt=2*n+1; nume=1; rep(i,1,n){ cin>>cost[i]; int cnt=0; rep(j,1,p){ cin>>in[i][j]; if(in[i][j]!=1) cnt++; } if(cnt==p) add(ss,i,INF); cnt=0; rep(j,1,p){ cin>>out[i][j]; if(out[i][j]==1) cnt++; } if(cnt==p) add(i+n,tt,INF); add(i,i+n,cost[i]); } rep(i,1,n){ rep(j,1,n){ if(i==j) continue; int cnt=0; rep(k,1,p){ if(in[j][k]!=2&&in[j][k]!=out[i][k]){ cnt++; break; } } if(cnt==0) add(i+n,j,INF); } } int ans=0; while(bfs()) ans+=dfs(); if(ans==0) cout<<"0 0 "; else { int cnt=0; for(int i=2;i<=nume;i+=2){ if(abs(e[i].pre-e[i].to)!=n&&e[i].to>ss&&e[i].pre>ss&&e[i].pre<tt&&e[i].to<tt&&e[i^1].cap!=0){ a[cnt++]=i; } } cout<<ans<<' '<<cnt<<' '; rep(i,0,cnt-1){ cout<<e[a[i]].pre-n<<' '<<e[a[i]].to<<' '<<e[a[i]^1].cap<<' '; } } #ifdef test fclose(stdin);fclose(stdout);system("out.txt"); #endif return 0; }