和自己的比起来，感觉大牛的代码要精悍的多啊。
代码如下：
#include <stdio.h>
#include <string.h>
#define maxn 250
struct Map
{
int f;
int c;
}map[maxn][maxn];
int pre[maxn];
int q[maxn*maxn];
int v[maxn];
int N,M;
int s,t;
int abs( int x ){ return x > 0 ? x : -x ; }
int min( int x, int y ){ return x < y ? x : y; }
void init()
{
int i, S, E, C;
memset( map, 0, sizeof(map) );
for(i=0;i<N;i++)
{
scanf( "%d%d%d", &S, &E, &C );
map[S][E].c += C;
}
}
void solve()
{
int i,j;
int head,tail;
s = 1;
t = M;
while(true)
{
memset( pre, 0, sizeof(pre) );
head = 0, tail = 1;
q[0] = s;
v[s] = 1000000000;
pre[s] = s;
while( head < tail && pre[t] == 0 )
{
i = q[head];
for( j = 1; j <= M; j++ )
{
if( pre[j] == 0 )
{
if( map[i][j].f < map[i][j].c )
pre[j] = i , q[tail++] = j , v[j] = min( v[i], map[i][j].c-map[i][j].f );
else if( map[j][i].f > 0 )
pre[j] = -i, q[tail++] = j , v[j] = min( v[i], map[j][i].f );
}
}
head++;
}
if( pre[t] == 0 )break;
i = t;
while( i != s )
{
j = abs( pre[i] );
if( pre[i] > 0 )map[j][i].f += v[t];
else map[i][j].f -= v[t];
i = j;
}
}
int ans = 0;
for( i = 1; i <= M; i++ )ans += map[s][i].f;
printf("%d\n",ans);
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
init();
solve();
}
return 0;
}
第一次写网络最大流算法，居然做对了。
该算法要用到 Dijkstra 算法。
每次用Dijkstra算法求的一条可通过的路后，找出该路上面的最小的权值 MIN，然后将该路径上的每条边的权值 减去 MIN ，反方向的权值加 MIN （ 例如：e( v1, v2 ) 是路径上面的一条边，则Map[v1][v2] -= MIN, Map[v2][v1] += MIN ). 累计MIN， 其最后的值就是所要求的最大流。
当最后 在图中找不到连接 1, n 两点的路径时，算法完毕。
//2019083 whitesea 1273 Accepted 224K 15MS C++ 1880B 2007-03-22 14:56:03
// PKU 1273 网络最大流
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
#include<stdio.h>
#include<string.h>
#define MAX 210
int Map[MAX][MAX];
int n, M, SUM, Path[MAX], distance[MAX], Min;
int IN(){
int i, x, y, d;
if( scanf( "%d %d", &M, &n ) == EOF )return 0; // M 是 边的数目， n 是点的数目
memset( Map, 0, sizeof( Map ) );
for( i = 1; i <= M; i++ ){
scanf( "%d %d %d", &x, &y, &d ); // 点x 到点y流量为 d
Map[x][y] += d;
}
return 1;
}
void Dijkstra(){
int mindis, i, j, u, s[MAX];
for( i = 1; i <= n; i++ ){
distance[i] = Map[1][i];
s[i] = 0;
if( i != 1 && distance[i] > 0 )Path[i] = 1;
else Path[i] = -1;
}
s[1] = 1;
for( i = 2; i <= n; i++ ){
mindis = 0;
for( j = 1; j <= n; j++ ){
if( s[j] == 0 && distance[j] > mindis ){
u = j;
mindis = distance[j];
}
}
if( mindis == 0 )return;
s[u] = 1;
for( j = 1; j <= n; j++ ){
if( s[j] == 0 && Map[u][j] > 0 && distance[u] + Map[u][j] > distance[j] ){
distance[j] = distance[u] + Map[u][j];
Path[j] = u;
}
}
}
}
void Find(){
int s, t;
Min = 2000000000;
s = n;
t = Path[n];
while( t != -1 ){
if( Map[t][s] < Min )Min = Map[t][s];
s = t;
t = Path[t];
}
}
void Change(){
int s, t;
s = n;
t = Path[n];
while( t != -1 ){
Map[t][s] -= Min;
Map[s][t] += Min;
s = t;
t = Path[t];
}
}
void SOLVE(){
int i, j, k;
SUM = 0;
while( 1 ){
Dijkstra();
if( Path[n] == -1 )return;
Find();
SUM += Min;
Change();
}
}
void OUT(){
printf( "%d\n", SUM );
}
int main(){
while( IN() ){
SOLVE();
OUT();
}
return 0;
}
做ACM 已经有快一年了，终于在PKU做满200题， 发帖纪念下，鼓励自己再接再厉。这一年发生的变化还真大啊，一不小心从一个新生变成了老生，从一个新手变成了老队员。想起来这一年来，感觉收获还是很大的。在这里我要特别感谢XC Azg Taney Stone CB ,他们给了我帮助与鼓励，也要感谢我的队友Lvyun Hailer，他们给了我很多的帮助。在做ACM 这个方面，我们学校一直很差，在06~07的全国三个赛区都掺败而归。现在我得努力，我的队友得努力，CUG 的ACMER 都得努力。让我们来把CUG 的ACM 做好， 努力吧，加油吧！