#include <stdio.h>
#include <string.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 201
#define MAXQSIZE 1000
#define MAX_INT 2000000
#define min(a, b) (a) < (b) ? (a) : (b)
int graph[N][N];
int n;
int queue[MAXQSIZE];
int front, rear;
int level[N];
int parent[N]; /* bfs过程中保存增广路径的路线 */
int augment[N]; /* augment[u表示]从源点到定点u的最小流量 */
void push(int e)
{
if ((rear+1) % MAXQSIZE == front) {
printf("queue is full...\n");
exit(0);
}
queue[rear] = e;
rear = (rear+1) % MAXQSIZE;
}
int pop()
{
int e;
e = queue[front];
front = (front+1) % MAXQSIZE;
return e;
}
void init_queue()
{
front = rear = 0;
}
int bfs(int s, int e)
{
int u, v;
init_queue();
memset(level, -1, sizeof(level));
push(s);
level[s] = 0;
while (front != rear) {
u = pop();
if (u == e) {
for (v = s; v <= e; v++) {
debug("level[%d] = %d\n", v, level[v]);
}
return 1;
}
for (v = 0; v <= e; v++) {
if (level[v] == -1 && graph[u][v] > 0) {
push(v);
level[v] = level[u] + 1;
}
}
}
return 0;
}
int dinic(int s, int e)
{
int u, v, max_flow, aug, w, degree;
max_flow = 0;
augment[s] = MAX_INT;
while (bfs(s, e)) {
u = s;
parent[s] = -1;
while (u != -1) { /* 如果u回溯到-1, 结束 */
if (u == e) { /* 找到一条增广路径 */
max_flow += augment[e];
aug = augment[e];
debug("找到一条增广路径, augment = %d\n", aug);
for (v = e, w = parent[e]; v > s; v = w, w = parent[w]) {
debug("%d<--", v);
graph[w][v] -= aug;
graph[v][w] += aug;
augment[v] -= aug;
if (graph[w][v] == 0) u = w;
}
debug("%d\n", v);
}
/* 从顶点u往下找邻接点 */
degree = 0;
for (v = s; v <= e; v++) {
if (graph[u][v] > 0 && (level[u]+1) == level[v]) {
augment[v] = min(augment[u], graph[u][v]);
parent[v] = u;
degree++;
u = v;
break;
}
}
if (degree == 0) { /* 没有邻接点, 回溯到上一个点 */
debug("顶点%d走不通\n", u);
level[u] = MAX_INT;
u = parent[u];
}
}
}
return max_flow;
}
int main()
{
int m, u, v, w;
while (scanf("%d", &m) != EOF) {
memset(graph, 0, sizeof(graph));
scanf("%d", &n);
while (m--) {
scanf("%d %d %d", &u, &v, &w);
graph[u-1][v-1] += w;
}
printf("%d\n", dinic(0, n-1));
}
return 0;
}
分享到:
相关推荐
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj2516代码最小费用最大流
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ各题算法分类和题目推荐.pdf
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
供初学编程基本算法的人练习使用,在poj.grids.cn上
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
关于C++ 算法 北大网站POJ 八数码问题
北大POJ中级-基本算法 解题报告+AC代码
Dinic多路增广pascal源码 poj 1273格式
用贪心算法解决POJ 1065的木棍处理问题
poj1113 melkman算法求凸包, 使用STL
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目