本文共 1151 字，大约阅读时间需要 3 分钟。
题目链接：
题目大意：
给出一些渠道，每个渠道有一个走向和容量，问最终汇集到溪流中的水的总量
题目分析：
裸裸的网络流的最大流，模板题
代码如下：
#include#include #include #include #include #define MAX 207#define INF 0x3f3f3f3fusing namespace std;int n,m;int s[MAX][MAX];int d[MAX];bool bfs ( ){ queue q; memset ( d , -1 , sizeof ( d ) ); d[1] = 0; q.push ( 1 ); while ( !q.empty() ) { int v = q.front(); q.pop(); for ( int i = 1 ; i <= n ; i++ ) if ( d[i] == -1 && s[v][i] ) { d[i] = d[v]+1; q.push ( i ); } } return d[n] != -1;}int dfs ( int v , int cur_flow ){ int dt = cur_flow; if ( v == n ) return cur_flow; for ( int i = 1 ; i <= n ; i++ ) if ( s[v][i] > 0 && d[v]+1 == d[i] ) { int flow = dfs ( i , min ( dt , s[v][i] ) ); s[v][i] -= flow; s[i][v] += flow; dt -= flow; } return cur_flow - dt;}int dinic ( ){ int cur_flow, ans = 0; while ( bfs() ) { while ( cur_flow = dfs ( 1 , INF ) ) ans += cur_flow; } return ans;}int main ( ){ while ( ~scanf ( "%d%d" , &m , &n ) ) { int u,v,c; memset ( s , 0 , sizeof ( s ) ); while ( m-- ) { scanf ( "%d%d%d" , &u , &v , &c ); s[u][v] += c; } //cout << "YES" << endl; printf ( "%d\n" , dinic() ); }}
转载地址：http://tpvjn.baihongyu.com/