#include <stdio.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 102
#define MAX_INT 2000000
#define min(a, b) ((a) < (b) ? (a) : (b))
int graph[N][N];
int h[N];
int e[N];
int n;
int push_relabel(int s, int t)
{
int max_flow, u, v, d, done, relabel, min_height;
memset(h, 0, sizeof(h));
memset(e, 0, sizeof(e));
h[s] = n;
for (u = 1; u <= t; u++) {
if (graph[s][u] > 0) {
e[u] = graph[s][u];
e[s] -= graph[s][u];
graph[u][s] = graph[s][u];
graph[s][u] = 0;
}
}
for (;;) {
done = 1;
for (u = s+1; u < t; u++) {
if (e[u] > 0) {
done = 0;
//先假设顶点u需要relabel
relabel = 1;
for (v = s; v <= t && e[u] > 0; v++) { /* 检查能push的顶点 */
if (graph[u][v] > 0 && h[u] > h[v]) {
//push
relabel = 0;
d = min(graph[u][v], e[u]);
e[u] -= d;
e[v] += d;
graph[u][v] -= d;
graph[v][u] += d;
debug("push %d --%d--> %d, e[%d] = %d\n", u, d, u, u, e[u]);
}
}
//没有可以push的顶点,执行relabel
if (relabel) {
//relabel
min_height = MAX_INT;
for (v = s; v <= t; v++) {
if (graph[u][v] > 0 && h[v] < min_height) {
min_height = h[v];
}
}
h[u] = 1 + min_height;
debug("relabel %d height to %d\n", u, h[u]);
}
}
}
if (done) { /* 除源点和汇点外,每个顶点的e[i]都为0 */
max_flow = 0;
for (u = s; u <= t; u++) {
if (graph[t][u] > 0) {
max_flow += graph[t][u];
}
}
break;
}
}
return max_flow;
}
int main()
{
int np, nc, m, u, v, w;
while (scanf("%d", &n) != EOF) {
n += 2; /* 添加源点和汇点 */
scanf("%d %d %d", &np, &nc, &m);
memset(graph, 0, sizeof(graph));
//输入m条边
while (m--) {
scanf(" (%d,%d)%d", &u, &v, &w);
graph[u+1][v+1] = w;
}
//输入np个power station
while (np--) {
scanf(" (%d)%d", &u, &w);
graph[0][u+1] = w;
}
//输入nc个consumer
while (nc--) {
scanf(" (%d)%d", &u, &w);
graph[u+1][n-1] = w;
}
printf("%d\n", push_relabel(0, n-1));
}
return 0;
}
分享到:
相关推荐
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1459-Power Network 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ3211--Washing Clothes
POJ水题集-----50道左右-----增加自信啊..
北大POJ中级-基本算法 解题报告+AC代码
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ初级题-数据结构:解题报告+AC代码
poj题目分类--acmer做题极有用资源
POJ3259--Wormholes,使用bellman方法。
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
北大POJ3414-Pots 解题报告+AC代码
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
poj 2827 Auto-Calculation Machine.md
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码