首页 > 代码库 > POJ 3436 ACM Computer Factory (最大流 + 输出路径)
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; }
POJ 3436 ACM Computer Factory (最大流 + 输出路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。