POJ 3436 ACM Computer Factory （最大流 + 输出路径）
POJ 3436 ACM Computer Factory
链接：http://poj.org/problem?id=3436题意：每台电脑有P部分，可以通过不同的机器来进行加工。有N台机器，每台机器用2 P +1 个整数来描述：Qi Si,1 Si,2 ... Si,p Di,1 Di,2. .. Di,p，其中Qi 指定了机器的性能，表示每小时加工的电脑数量。Si,j 为第j 部分的输入规格，0表示该部分不能被加工过，1表示该部分必须被加工过，2表示都可以。Di,k 为第k 部分的输出规格。0表示经过该机器不加工，1表示该机器加工该部分。1≤P≤10，1≤N≤50，1≤Qi≤10000。
思路：建立一个源点，只要每台机器的s部分没有1，即从源点向其连边，流量为该机器的效率。建立一个汇点，只要每台机器的D部分全部为1，则向汇点连边，流量为机器的效率。如果某个机器的输出部分符合某个机器的输入部分，则两者连边，流量为min(Qi, Qj)。观察发现如果 j 机器的输入部分为2，这 i 机器输出部分随意，否则j的输出部分必须与输入部分相同。
PS：这道题也可以拆点来做，将每个机器的输入部分和输出部分分开，并连边，流量为机器效率，然后不同机器之间匹配的话，流量就为INF。同时源点和汇点与机器连边时，流量也为INF。
代码：
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define LINF (1LL<<60)
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 60;
const int maxm = 20000;
int st, ed, n;
int P, N;
int S[maxn][10], D[maxn][10], Q[maxn];
struct node {
int v; // vertex
int cap; // capacity
int flow; // current flow in this arc
int nxt;
} e[maxm * 2];
int g[maxn], cnt;
void add(int u, int v, int c) {
e[++cnt].v = v;
e[cnt].cap = c;
e[cnt].flow = 0;
e[cnt].nxt = g[u];
g[u] = cnt;
e[++cnt].v = u;
e[cnt].cap = 0;
e[cnt].flow = 0;
e[cnt].nxt = g[v];
g[v] = cnt;
}
bool check(int x, int y) {
for (int i = 0; i < P; i++) if (S[y][i] != 2) {
if (S[y][i] != D[x][i]) return false;
}
return true;
}
void init() {
mem(g, 0);
cnt = 1;
scanf("%d%d", &P, &N);
st = 0, ed = N + 1;
int ok;
for (int i = 1; i <= N; i++) {
scanf("%d", Q + i);
ok = 0;
for (int j = 0; j < P; j++) {
scanf("%d", S[i] + j);
if (S[i][j] == 1) ok++;
}
if (!ok) add(st, i, Q[i]);
ok = 0;
for (int j = 0; j < P; j++) {
scanf("%d", D[i] + j);
if (D[i][j] == 1) ok++;
}
if (ok == P) add(i, ed, Q[i]);
}
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (check(i, j)) add(i, j, min(Q[i], Q[j]));
if (check(j, i)) add(j, i, min(Q[i], Q[j]));
}
}
n = N + 3;
}
int dist[maxn], numbs[maxn], q[maxn];
void rev_bfs() {
int font = 0, rear = 1;
for (int i = 0; i <= n; i++) { //n为总点数
dist[i] = maxn;
numbs[i] = 0;
}
q[font] = ed;
dist[ed] = 0;
numbs[0] = 1;
while(font != rear) {
int u = q[font++];
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue;
dist[e[i].v] = dist[u] + 1;
++numbs[dist[e[i].v]];
q[rear++] = e[i].v;
}
}
}
int maxflow() {
rev_bfs();
int u, totalflow = 0;
int curg[maxn], revpath[maxn];
for(int i = 0; i <= n; ++i) curg[i] = g[i];
u = st;
while(dist[st] < n) {
if(u == ed) { // find an augmenting path
int augflow = INF;
for(int i = st; i != ed; i = e[curg[i]].v)
augflow = min(augflow, e[curg[i]].cap);
for(int i = st; i != ed; i = e[curg[i]].v) {
e[curg[i]].cap -= augflow;
e[curg[i] ^ 1].cap += augflow;
e[curg[i]].flow += augflow;
e[curg[i] ^ 1].flow -= augflow;
}
totalflow += augflow;
u = st;
}
int i;
for(i = curg[u]; i; i = e[i].nxt)
if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
if(i) { // find an admissible arc, then Advance
curg[u] = i;
revpath[e[i].v] = i ^ 1;
u = e[i].v;
} else { // no admissible arc, then relabel this vertex
if(0 == (--numbs[dist[u]])) break; // GAP cut, Important!
curg[u] = g[u];
int mindist = n;
for(int j = g[u]; j; j = e[j].nxt)
if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != st)
u = e[revpath[u]].v; // Backtrack
}
}
return totalflow;
}
int out[maxm][3], tot = 0;
void get_out() {
for (int u = 1; u < ed; u++) {
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i].v != ed && e[i].flow > 0) {
out[tot][0] = u;
out[tot][1] = e[i].v;
out[tot++][2] = e[i].flow;
}
}
}
}
int main () {
init();
printf("%d ", maxflow());
get_out();
printf("%d\n", tot);
for (int i = 0; i < tot; i++) {
printf("%d %d %d\n", out[i][0], out[i][1], out[i][2]);
}
return 0;
}
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。