http://poj.org/problem?id=1273题意描述：给N个下水道和每条下水道的最大流量，M个节点，要求求出从节点1到节点M的最大流量。
最赤裸的网络流，不断找出增广路增广即可。找增广路时，这里用的深度优先搜索。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 210
#define MAX 1000000000
int mp[LEN][LEN];
int tc[LEN];//记录dfs的路径
int tclen;
int gd[LEN];//记录某个节点是否访问过
int endDFS;//记录是否找到新的增广路
int sum;//当前流
int mf;//增广路上最小的那条边的大小
int N, M;
void traceBack()//找到增广路后，用该函数修改mp[][]
{
int i, j;
int f, t;
for(i = 1; i < tclen; i++)
{
f = tc[i - 1];
t = tc[i];
mp[f][t] -= mf;
mp[t][f] += mf;
}
}
void DFS(int m)
{
int i, j;
if(endDFS)
return;
for(i = 1; i <= M; i++)
{
if(gd[i] == 0 && mp[m][i] > 0)
{
if(i == M)
{
if(mp[m][i] < mf)
mf = mp[m][i];
tc[tclen++] = i;
gd[i] = 1;
endDFS = 1;
traceBack();
sum += mf;
return;
}
else
{
if(mp[m][i] < mf)
mf = mp[m][i];
tc[tclen++] = i;
gd[i] = 1;
DFS(i);
tclen--;
}
}
}
}
int main()
{
int i, j;
int s, e, c;
while(scanf("%d%d", &N, &M) != EOF)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < N; i++)//read data
{
scanf("%d%d%d", &s, &e, &c);
mp[s][e] += c;
}
sum = 0;//init sum
while(1)//find Augmenting Path
{
memset(gd, 0, sizeof(gd));
mf = MAX;
gd[1] = 1;
tc[0] = 1;
tclen = 1;
endDFS = 0;
DFS(1);
if(endDFS == 0)
break;
}
printf("%d\n", sum);
}
//system("pause");
return 0;
}
posted on 2012-09-07 21:29
小鼠标 阅读(271)
评论(1) 编辑 收藏 引用 所属分类:
图论