转：
有N台机器，每台机器有P部分，每部分都有各自的输入、输出规格，因此一台机器有P个输入规格，P个输出规格。每台机器有2*P+1种参数去描述：第一个参数Q：该机器的容量；接下来P个参数S：该机器各部分的输入规格；接下来P个参数D：该机器各部分的输出规格。
其中输入规格有三种情况：0,1,2
0：该部分不能存在
1：该部分必须保留
2：该部分可有可无
输出规格有2种情况：0,1
0：该部分不存在
1：该部分存在
注意：本题可以只有一次输入，一次输出，还有Sample I/O这段英文不用输入输出
Sample input:
P N （N台机器，每台机器有P部分）
接着输入N行，其实每行都是一个结点的信息
每一行的格式为 一个Q P个S P个D
其中Q为当前结点的容量，S都是当前结点的输入规格，D都是输出规格
Sample output:
第一行的两个数字分别表示：最大流的值，流量发生变化的边数M（和s还有t关联的边不在其内，那些不属于原有的边，是附加边）
接下来有M行，每一行都有三个数字，A B W
A B为流量发生变化的边的端点，W为流量的变化值（每条边初始流量为0，最终流量就是找到最大流时的流量）
若图不连通，则输出0 0
解题思路:
首先构造图：
添加两个超级源s,超级汇t
如果某个节点(i)的输入部分不含1，则添加一条s->i路径，容量为Qi;
如果某个节点(j)输出全为1，则添加一条j->t路径，容量为Qj;
如果节点i的输出与j的输入不存在冲突(输出与输入对应位置的和不能为1)，则添加一条i->j的路径，容量为min(Qi, Qj).
PS：输出与输入对应位置的和不能为1，就是说组合为可以为00，11， 21或20，但不能是01
解题方法：
就是最大流问题
#include#include #include #include using namespace std; const int INF = 0x3f3f3f3f; int n,p; int in[55][25]; int s,t; int cap[55][55],tmp[55][55]; int pre[55]; int maxflow() { int flow = 0; queue que; for(;;) { memset(pre,-1,sizeof(pre)); while(!que.empty()) que.pop(); que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = 0; i <= n+1; i++) { if(cap[u][i] && pre[i] == -1) { pre[i] = u; que.push(i); } } } if(pre[t] == -1) break; int minflow = INF; for(int u = t; u != s; u = pre[u]) { if(minflow > cap[pre[u]][u]) minflow = cap[pre[u]][u]; } for(int u = t; u != s; u = pre[u]) { cap[pre[u]][u] -= minflow; cap[u][pre[u]] += minflow; } flow += minflow; } return flow; } int main() { while(~scanf("%d %d",&p,&n)) { for(int i = 1; i <= n; i++) { scanf("%d",&in[i][0]); for(int j = 1; j <= p+p; j++) scanf("%d",&in[i][j]); } memset(cap,0,sizeof(cap)); s = 0; t = n+1; for(int i = 1; i <= n; i++) { bool flag = true; for(int j = 1; j <= p; j++) { if(in[i][j] == 1) { flag = false; break; } } if(flag) cap[s][i] = in[i][0]; flag = true; for(int j = p+1; j <= p+p; j++) { if(in[i][j] == 0) { flag = false; break; } } if(flag) cap[i][t] = in[i][0]; for(int j = 1; j <= n; j++) { if(i != j) { flag = true; for(int k = 1; k <= p; k++) { if(in[i][k+p]+in[j][k] == 1) { flag = false; break; } } if(flag) cap[i][j] = min(in[i][0], in[j][0]); } } } memcpy(tmp,cap,sizeof(cap)); int flow = maxflow(); int out[55][5]; int cnt = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j && cap[i][j] < tmp[i][j]) { out[cnt][0] = i; out[cnt][1] = j; out[cnt][2] = tmp[i][j]-cap[i][j]; cnt++; } } } printf("%d %d\n",flow,cnt); for(int i = 0; i < cnt; i++) { printf("%d %d %d\n",out[i][0],out[i][1],out[i][2]); } } return 0; }