#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
#define N 210
int point, edge;
int graph[N][N];
int pre[N];
int result= 0;
void update( int mflow )
{
int b= point;
result+= mflow;
while( pre[b]!= 0 )
{
graph[ pre[b] ][ b]-= mflow;
graph[b ][ pre[b] ]+= mflow;
b= pre[b];
}
}
void bfs()
{
while( true )
{
bool visite[N]= { false };
int minflow[N];
queue<int> q;
q.push( 1 );
visite[1]= true;
minflow[1]= INT_MAX;
memset( pre, 0, sizeof(pre) );
while( !q.empty() )
{
int t= q.front();
q.pop();
for( int j= 1; j<= point; ++j )
if( !visite[j] && graph[t][j]> 0 )
{
minflow[j]= min( minflow[t], graph[t][j] );
pre[j]= t;
q.push( j );
visite[j]= true;
}
if( pre[point]> 0 ) break;
}
if ( pre[point]> 0 ) update( minflow[point] );
else break;
}
}
int main()
{
while( scanf("%d%d", &edge, &point )!= EOF )
{
memset( graph, 0, sizeof(graph) );
for( int i= 0; i< edge; ++i )
{
int a, b, d;
scanf("%d%d%d", &a, &b, &d );
graph[a][b]+= d; // not just one ditch
}
result= 0;
bfs();
printf("%d\n", result );
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Min(a,b) ( (a)< (b)?(a): (b) )
int m, n;
int map[210][210];
bool visite[210];
int path[210], dist[210], minflow[210];
int max_flow()
{
for( int i= 0; i<= n; ++i )
{
visite[i]= false; dist[i]= 0;
path[i]= 1; minflow[i]= 0;
}
visite[1]= true; minflow[1]= 1<< 30;
for( int i= 1; i<= n; ++i )
dist[i]= map[1][i], minflow[i]= map[1][i];
for( int i= 1; i< n; ++i )
{
int min= 1<< 30, t= -1;
for( int j= 1; j<= n; j++ )
if( !visite[j] && min> dist[j] && dist[j]> 0 ) min= dist[j],t= j;
if( t== -1 ) break;
visite[t]= true;
for( int j= 1; j<= n; ++j )
if( !visite[j] && map[t][j]> 0 &&
( dist[t]> 0 && dist[t]+ map[t][j]< dist[j] || dist[j]== 0 ) )
{
dist[j]= dist[t]+ map[t][j];
path[j]= t;
minflow[j]= Min( map[t][j], minflow[t] );
}
}
return minflow[n];
}
int update()
{
int f, total= 0;
while( ( f= max_flow() )!= 0 )
{
int j= n;
while( path[j]!= j )
{
map[ path[j] ][j]-= f;
map[j][ path[j] ]+= f;
j= path[j];
}
total+= f;
}
return total;
}
int main()
{
while( scanf("%d%d",&m,&n)!= EOF )
{
memset( map, 0, sizeof(map) );
for( int i= 0; i< m; ++i )
{
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
map[a][b]+= c;
}
printf("%d\n", update() );
}
return 0;
}
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int m, n;
int map[210][210], h[210],wt[210], flow[210][210];
int max_flow()
{
memset( wt, 0, sizeof(wt) );
memset( h, 0, sizeof(h) );
queue<int> Q;
Q.push(1); wt[1]= 1<<30; wt[n]= -1<<30;
h[1]= n;
int total= 0;
while( !Q.empty() )
{
int u= Q.front(); Q.pop();
for( int v= 1; v<= n; ++v )
{
int f= min( wt[u], map[u][v] );
if( f> 0 && ( u== 1 || h[u]== h[v]+ 1 ) )
{
map[u][v]-= f, map[v][u]+= f;
wt[u]-= f, wt[v]+= f;
if( v== n ) total+= f;
if( v!= 1 && v!= n ) Q.push(v);
}
}
if( u!= 1 && u!= n && wt[u]> 0 )
{
h[u]++;
Q.push(u);
}
}
printf("%d\n", total );
}
int main()
{
while( scanf("%d%d",&m,&n)!= EOF )
{
memset( map, 0, sizeof(map) );
for( int i= 0; i< m; ++i )
{
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
map[a][b]+= c;
}
max_flow();
}
return 0;
}
posted on 2008-11-04 14:15
Darren 閱讀(223)
評論(1) 編輯 收藏 引用