Posted on 2008-08-01 14:35
Hero 阅读(86)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/*
ID: wangzha4
LANG: C++
TASK: ditch
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
double fmax( double a, double b )
{
if( a - b > 0 ) return a ;
else return b ;
}
double fmin( double a, double b )
{
if( a - b < 0 ) return a ;
else return b ;
}
int fmax( int a, int b )
{
if( a > b ) return a ;
else return b ;
}
int fmin( int a, int b )
{
if( a < b ) return a ;
else return b ;
}
int fpow( int a, int b )
{
int reval = 1 ;
for( int i=1; i<=b; i++ )
reval *= a ;
return reval ;
}
const int INF = 1000000 ;
const int size = 210 ;
int inn ;//边的数量
int inm ;//点的数量
int pren[size] ;//点的前驱节点
int ncap[size] ;//每个点的最大流量(流出量)
int visit[size] ;//标记该点是否被访问过
int flow[size][size] = {0} ;//边的流量
int agument()
{//寻找增广路径,返回路径容量(瓶颈容量)
memset( visit, 0, sizeof(visit) ) ;
memset( ncap, 0, sizeof( ncap ) ) ;
int maxncap = 0 ;//最大流量点的流量
int maxn = -1 ;//最大流量点的标号
ncap[1] = INF ;//初始化原点的流量为无穷大,保证从原点开始寻找
while( true ) {
maxncap = 0 ; maxn = -1 ;
for( int i=1; i<=inm; i++ ) {
if( !visit[i] && ncap[i] > maxncap ) {
maxncap = ncap[i] ; maxn = i ;
}
}//找到拥有最大流量且没有被访问过的点
if( -1 == maxn ) return 0 ;//没有找到新的增广路径
if( maxn == inm ) break ;//已经找到一条新的增广路径
visit[maxn] = 1 ;//标记这个点已经被访问过
for( int i=1; i<=inm; i++ ) {//对maxn的相邻节点进行更新操作
if( flow[maxn][i]>ncap[i] && maxncap>ncap[i] ) {
//节点的流量为边流量和路径流量的最小值
ncap[i] = fmin( flow[maxn][i], maxncap ) ;
pren[i] = maxn ;//节点i的前驱节点为maxn
}
}
}//while( true )
maxncap = ncap[inm] ;//路径容量即为汇点的流量
for( int i=inm; i>1; i=pren[i] ) {
int curnode = pren[i] ;//i的前驱节点
flow[curnode][i] -= maxncap ;//正向边+路径容量
flow[i][curnode] += maxncap ;//反向边-路径容量
}
return maxncap ;//返回路径容量
}
int main()
{
freopen( "ditch.in", "r", stdin ) ;
freopen( "ditch.out","w",stdout ) ;
memset( flow, 0, sizeof(flow) ) ;
scanf( "%d %d",&inn, &inm ) ;
int sn, en, f ;
for( int i=1; i<=inn; i++ ) {
scanf( "%d %d %d", &sn, &en, &f ) ;
flow[sn][en] += f ;
}//data input
int maxflow = 0 ; int addflow ;
while( ( addflow = agument() ) ) {//当路径容量不为0
maxflow += addflow ;
}
printf( "%d\n",maxflow ) ;
return 0 ;
}