最大流：两枚[poj1459poj3436]

说说建图吧…poj1459:

增加超级源点，超级汇点，跑一遍即可。

;const int MAX = 107;const int INF = 0xfffffff;struct node {int to;int cap;int rev;};vector<node> G[MAX];int level[MAX];bool vis[MAX];int n, np, nc, m, S, T;inline void add_edge(int u, int v, int c) {G[u].push_back((node){v, c, G[v].size()});G[v].push_back((node){u, 0, G[u].size() – 1});}// from S to T, with max cap: Cbool BFS(int S, int T) {queue<int> Q;Q.push(S);memset(level, -1, sizeof(level));level[S] = 0;while (!Q.empty()) {int p = Q.front();Q.pop();for (vector<node>::iterator it = G[p].begin(); it != G[p].end(); ++it) {if (level[it->to] < 0 && it->cap > 0) {level[it->to] = level[p] + 1;Q.push(it->to);if (it->to == T) return true;}}}return false;}int DFS(int u, int v, int c) {if (u == v) return c;int sum = 0, tmp;for (vector<node>::iterator it = G[u].begin(); it != G[u].end(); ++it) {if (level[it->to] == level[u] + 1 && it->cap > 0) {tmp = DFS(it->to, T, min(c – sum, it->cap));sum += tmp;it->cap -= tmp;G[it->to][it->rev].cap += tmp;}}return sum;}int dinic(int S, int T) {int sum = 0;while (BFS(S, T)) {memset(vis, false, sizeof(vis));sum += DFS(S, T, INF);}return sum;}int main() {while (~scanf(” %d %d %d %d”, &n, &np, &nc, &m)) {S = n, T = n + 1;for (int i = 0; i <= T; ++i) G[i].clear();int a, b, c;for (int i = 0; i < m; ++i) {scanf(” (%d,%d)%d”, &a, &b, &c);add_edge(a, b, c);}for (int i = 0; i < np; ++i) {scanf(” (%d)%d”, &a, &c);add_edge(S, a, c);}for (int i = 0; i < nc; ++i) {scanf(” (%d)%d”, &a, &c);add_edge(a, T, c);}printf(“%d\n”, dinic(S, T));}return 0;}poj3436 ACM Computer Factory:题意：

好多机器生产电脑，每台机器对应的P个元器件。 输入： 0表示不能有 1表示一定要有 2表示可有可无 输出： 0表示没有 1表示有 另外还有一个流量值Q,即生产能力。 举例说明，如果有3种元器件，那么机器{15, [1, 2, 0], [1, 0, 1]}表示它可同时艹(即加工，编者注)15台产品{本题是生产电脑}，并且拿给它加工的产品必须有元件1(不然可能产生故障)，元件2可有可无(不影响)，一定不能有元件3(不然卡住了就拔不出来了)；同时，经过它加工后的产品会剩下元件1和元件3，，不会有元件2. 深入理解后可以建图了： ①增加超级源点，超级汇点。对每个机器判断它是否能作为源点（输入的P的元器件要求不为’1’），是否能作为汇点（输出中P种原件均为’1’，也就是产品必须是完整哒）。对应与源汇点连边，容量INF。 ②对每个机器，拆点，中间流量为对应那台机器的生产能力。 ③ 两两检查每对机器，我们对每对组合判断一下： 如果对某元器件，机器1输出为x,机器2要求输入为y，那么 x,y= 0,0: OK 0,1: 不行 0,2:行 1,0：不行 1,1：行 1,2：行 所以只要检查

x+y==1?不行:行

即可。

;const int MAX = 55;const int INF = 0xfffffff;int G[MAX << 1][MAX << 1];int in[MAX][MAX], out[MAX][MAX];int level[MAX << 1];int N, P;struct o_o {int u;int v;int c;};bool BFS(int S, int T) {queue<int> Q;memset(level, -1, sizeof(level));Q.push(S);level[S] = 0;while (!Q.empty()) {int p = Q.front();Q.pop();if (p == T) return true;//这里务必保证T的标号最大for (int i = 0; i <= T; ++i) {if (level[i] == -1 && G[p][i] > 0) {level[i] = level[p] + 1;Q.push(i);}}}return false;}int DFS(int s, int t, int flow) {//printf(“vis %d—————-\n”, S);if (s == t) return flow;int sum = 0, tmp;for (int i = 0; i <= t; ++i) {if (level[i] == level[s] + 1 && G[s][i] > 0) {tmp = DFS(i, t, min(flow – sum, G[s][i]));sum += tmp;//printf(“(%d,%d)\n”, s, sum);G[s][i] -= tmp;G[i][s] += tmp;}}return sum;}int dinic(int S, int T) {int sum = 0;while (BFS(S, T)) {sum += DFS(S, T, INF);}return sum;}int main() {int GT[MAX << 1][MAX << 1];while (~scanf(” %d %d”, &P, &N)) {memset(G, 0, sizeof(G));for (int i = 1; i <= N; ++i) {//拆点scanf(” %d”, &G[i][i + N]);for (int j = 1; j <= P; ++j) {scanf(” %d”, &in[i][j]);}for (int j = 1; j <= P; ++j) {scanf(” %d”, &out[i][j]);}}int S = 0, T = N << 1 | 1;for (int i = 1; i <= N; ++i) {bool flag1 = true, flag2 = true;;for (int j = 1; j <= P; ++j) {if (in[i][j] == 1) {flag1 = false;}if (out[i][j] != 1) {flag2 = false;}}(int j = 1; j <= N; ++j) {if (i == j) continue;flag1 = true;for (int k = 1; k <= P; ++k) {if (out[i][k] + in[j][k] == 1) {flag1 = false;break;}}if (flag1) G[i + N][j] = INF;}}memcpy(GT, G, sizeof(G));int ans = dinic(S, T);vector<o_o> V;o_o u_u;if (ans) {for (int i = 1; i < T; ++i) {for (int j = 1; j < T; ++j) {if (G[i][j] < GT[i][j]) {u_u.u = i > N ? i – N : i;u_u.v = j > N ? j – N : j;u_u.c = GT[i][j] – G[i][j];if (u_u.u == u_u.v) continue;V.push_back(u_u);}}}printf(“%d %d\n”, ans, V.size());for (vector<o_o>::iterator it = V.begin(); it != V.end(); ++it) {printf(“%d %d %d\n”, it->u, it->v, it->c);}} else {puts(“0 0”);}}return 0;}

我喜欢旅游，喜欢离开自己过腻歪的城市，