http://poj.org/problem?id=3436
题意可以看vjudge里面的
假如a的输出结构等于b的输入结构，那么就可以连一条边。
边的容量是INF，但是点是有上限的，所以我们将点拆开，一个点变成两个点，中间有一条容量为点容量的线连接。
当然需要加上对于输入结构是0 0 0 0 ...的要连接超级源点和输出结构是 1 1 1 1 1.....的要链接超级汇点，容量依然是INF
本题使用dinic算法，我们可以使用一个m数组，记录dinic的价值变化，具体可以看代码，在有关地方都有标注
#include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> #include<iostream> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1e5; struct node { int to, val, nxt; }edges[maxn]; int head[maxn], deep[maxn]; int n, p; struct Dinic { int id, s, t; int m[200][200]; //记录 跟着一起加减 void init(int n1,int n2) { id = -1; s = n1; t = n2; //s: 源点 t：汇点 memset(head, -1, sizeof(head)); memset(m, 0, sizeof(m)); } void add_edge(int fro, int to, int val) { edges[++id].to = to; edges[id].val = val; edges[id].nxt = head[fro]; head[fro] = id; edges[++id].to = fro; edges[id].val = 0; edges[id].nxt = head[to]; head[to] = id; } bool bfs() { //建deep memset(deep, 0, sizeof(deep)); deep[s] = 1; queue<int> Q; Q.push(s); while (!Q.empty()) { int now = Q.front(); Q.pop(); for (int i = head[now]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (edges[i].val && deep[to] == 0) { deep[to] = deep[now] + 1; if (to == t) return 1; Q.push(to); } } } return 0; } int dfs(int point , int flow) { if (point == t) return flow; int lat_cost, cost = 0; for (int i = head[point]; i != -1; i = edges[i].nxt) { int to = edges[i].to; if (deep[to] == deep[point] + 1 && edges[i].val) { lat_cost = dfs(to, min(flow - cost, edges[i].val)); // ? if (lat_cost > 0) { m[point][to] += lat_cost; m[to][point] -= lat_cost; //记录路径 edges[i].val -= lat_cost; edges[i ^ 1].val += lat_cost; cost += lat_cost; if (flow == cost) break; } } } return cost; } void Output() { //输出路径 int cnt = 0; vector<int> r; for (int i = 2; i <= 2*p+ 1 ; i+=2) { for (int j = 1; j <= 2 * p + 1 ; j+=2) { if (j == i - 1) continue; if (m[i][j]) { cnt++; //cout << i / 2 << " " << (j + 1) / 2 <<" "<< m[i][j] << endl; r.push_back(i / 2); r.push_back((j + 1) / 2); r.push_back(m[i][j]); } } } cout << cnt << endl; for (int i = 0; i < cnt; i++) { cout << r[3 * i] << " " << r[3 * i + 1] <<" "<< r[3 * i + 2] << endl; } } int dinic() { int ans = 0; while (bfs()) { ans += dfs(s, INF); } return ans; } }; Dinic dic; int sfro[55][15], sto[55][15], val[55]; bool Check_beg(int i) { //检查是否与超级源点链接 for (int j = 1; j <= n; j++) { if (sfro[i][j]==1) { //等于0和2都可以，等于1就退出 return 0; } } return 1; } bool Check_end(int i) { //检查是否与超级汇点链接 for (int j = 1; j <= n; j++) { if (sto[i][j] == 0) return 0; } return 1; } int main() { while (scanf("%d %d", &n, &p)!=EOF) { dic.init(0, 2*p + 2); //因为点要裂开，所以点的数量要乘2 for (int i = 1; i <= p; i++) { scanf("%d", val + i); for (int j = 1; j <= n; j++) { scanf("%d", &sfro[i][j]); } for (int j = 1; j <= n; j++) { scanf("%d", &sto[i][j]); } } //总体应该*2 入： 2*i-1 出 2*i 汇点2*p+2 for (int i = 1; i <= p; i++) { dic.add_edge(2 * i - 1, 2 * i, val[i]); if (Check_beg(i)) { dic.add_edge(0, 2*i-1, INF); } if (Check_end(i)) { dic.add_edge(2*i, 2*p + 2, INF); } for (int j = 1; j <= p; j++) { if (i == j) continue; int ok = 1; for (int k = 1; k <= n; k++) { if (!(sto[i][k] == sfro[j][k] || sfro[j][k] == 2)) { ok = 0; break; } } if (ok == 1) { //建边 dic.add_edge(2*i, 2*j-1, INF); } } } cout << dic.dinic() << " "; dic.Output(); } }
