NJUSTOJ 1347 内功or外功
题目大意：中文
题目链接
代码：
/* * Problem ID : NJUSTOJ 1347 内功or外功* Author : Lirx.t.Una * Language : GCC * Run Time : 196 ms * Run Memory : 1704 KB
*/#pragma GCC optimize("O2")#include
#include
#include #define INF INT_MAX #define MAXNODEN 1002
#define MAXFLWN 20000#define MIN(x,y) ( (x) < (y) ? (x) : (y) )typedef struct {int v;int c;
} Flow;Flow flw[MAXFLWN];
int next[MAXFLWN];
int head[MAXNODEN];
int e;int lev[MAXNODEN];
int sum_lev[MAXNODEN];
int pre[MAXNODEN];
int aug[MAXNODEN];void
addflw( int u, int v, int c ) {flw[e].v = v;flw[e].c = c;next[e] = head[u];head[u] = e++;flw[e].v = u;flw[e].c = 0;next[e] = head[v];head[v] = e++;
}int
sap( int src, int des ) {int u, v;int ans;int minf;int minu;int f;int minlev;memset( lev, 0, ( des + 1 ) * sizeof(int));sum_lev[0] = ( des + 1 );memset( sum_lev + 1, 0, ( des + 1 ) * sizeof(int));for ( u = 0; u <= des; u++ )aug[u] = head[u];ans = 0;u = src;while ( lev[src] < ( des + 1 ) ) {if ( u == des ) {for ( minf = INF, u = src; u != des; u = flw[f].v )if ( f = aug[u], flw[f].c < minf ) {minf = flw[f].c;minu = u;}for ( u = src; u != des; u = flw[f].v ) {f = aug[u];flw[f].c -= minf;flw[f ^ 1].c += minf;}ans += minf;u = minu;}for ( f = aug[u]; f != -1; f = next[f] )if ( flw[f].c && lev[u] == lev[ flw[f].v ] + 1 )break;if ( f != -1 ) {v = flw[f].v;aug[u] = f;pre[v] = u;u = v;}else {if ( !( --sum_lev[ lev[u] ] ) )break;aug[u] = head[u];for ( minlev = ( des + 1 ), f = head[u]; f != -1; f = next[f] )if ( flw[f].c )minlev = MIN( minlev, lev[ flw[f].v ] );lev[u] = minlev + 1;sum_lev[ lev[u] ]++;if ( u != src )u = pre[u];}}return ans;
}int
main() {int n, m;int u, v, c;int ans;while ( ~scanf("%d%d", &n, &m) ) {memset(head, -1, ( n + 1 ) * sizeof(int));e = 0;while ( m-- ) {scanf("%d%d%d", &u, &v, &c);addflw( u, v, c );}ans = sap( 0, n );if ( !ans )puts("you need to study hard!");elseprintf("%d\n", ans);}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！