题目地址：http://poj.org/problem?id=3436
写了起码4hour+....
假设两个超级汇点源点，到000，和111点
因为p最大只有10，所以一个整数就能保存
保存点比较麻烦，一开始想的是map 给每个点一个id，但是两个相同的点，比如说010，不能看成同一个点，因为机器都不同，等下路径都找不了了
所以用in[]，out[]保存出来的点和进去的点，当out[u]==in[v]说明u-->v
还要输出路径，也就是协作关系：
1）方法一就是备份初始的图，当流量变少了，说明肯定流过
2）方法二就是根据剩下来的残余网络，如果反向边G[v][u]>0 ，说明u->v流过，这样可以省一个数组空间
然后我一直错的一个点就是，一直写超级源点到000而忽略了存在2的情况如020 ，超级汇点也是如此
#include<iostream>
#include<queue>
#include<cmath>#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=100+5;
const int INF=1000000000;
int G[maxn][maxn];
int PriG[maxn][maxn];
int prev[maxn]; //记录前驱节点，记录增广路径
bool vis[maxn];
int read(int k,int& x) //if k>0 in,else out
{bool s=false,t=false;if(k>0) s=true;else t=true;x=0;int n=1;for(int i=0;i<fabs(k);i++){cin>>n;x=x*10+n;if(k>0&&n==1) s=false; if(k<0&&n==0) t=false;}if(s) return 0; //is 000 注意其中有2也算 if(t) return 1; //is 111 return -1;
}
bool check(int n1,int n2)
{int i,j;for(;;){if(n1==0&&n2==0) break;i=n1%10,j=n2%10;if(i+j==1) return false;n1/=10;n2/=10;}return true;
}
int Augment(int s,int t) //增广
{queue<int> Q;bool isFound=false; //标记是否找到了增广路 memset(vis,false,sizeof(vis));memset(prev,-1,sizeof(prev));Q.push(s);vis[s]=true;while(!Q.empty()){int u=Q.front(); Q.pop();if(u==t) { //找到增广路径了 isFound=true;break;}for(int v=0;v<=t;v++)if(u!=v&&G[u][v]>0&&!vis[v]){prev[v]=u;vis[v]=true;Q.push(v); }}if(!isFound) return 0; //无路可走 int MinFlow=INF; int u=t;while(u!=s){ //计算途中最小流 MinFlow=min(MinFlow,G[prev[u]][u]);u=prev[u];}u=t;while(u!=s){G[prev[u]][u]-=MinFlow; //更新途径路的流量 G[u][prev[u]]+=MinFlow; //加上反向边 u=prev[u];}return MinFlow;
}
void printPath(int m)
{vector<int> s,e,w;for(int i=1;i<=m;i++) for(int j=1;j<=m;j++)if(i!=j&&PriG[i+m][j]>G[i+m][j]) //in->out 反向边{s.push_back(i);e.push_back(j);w.push_back(PriG[i+m][j]-G[i+m][j]);}cout<<s.size()<<endl;for(int i=0;i<s.size();i++)printf("%d %d %d\n",s[i],e[i],w[i]);
}
int in[maxn];
int out[maxn];
int main()
{int n,m;while(cin>>n>>m){int u,v,w;int s=0,t=2*m+1;for(int i=1;i<=m;i++){cin>>w;G[i][i+m]+=w; //1~m是in，m+1~2*m是out ，源点是0，汇点是2*m+1 if(read(n,in[i])==0) G[s][i]+=INF;if(read(-n,out[i])==1) G[i+m][t]+=INF; }for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(check(out[j],in[i])) G[j+m][i]+=INF;memcpy(PriG,G,sizeof(G));int MaxFlow=0;int aug;while(aug=Augment(s,t)) MaxFlow+=aug; //加上每次增广的流 cout<<MaxFlow<<' ';printPath(m);}return 0;
}