POJ_1273

    基础的最大流的题目，构建好图之后直接求解S到T的最大流即可。

#include
     
      #include
      
       #include
       
        #define MAXD 210#define MAXM 410#define INF 0x3f3f3f3fint N, M, first[MAXD], e, next[MAXM], v[MAXM], flow[MAXM];int S, T, d[MAXD], q[MAXD], work[MAXD];void add(int x, int y, int z){    v[e] = y, flow[e] = z;    next[e] = first[x], first[x] = e ++;    }void init(){    int i, x, y, z;    S = 1, T = N;    memset(first, -1, sizeof(first[0]) * (T + 1)), e = 0;    for(i = 0; i < M; i ++)    {        scanf("%d%d%d", &x, &y, &z);        add(x, y, z), add(y, x, 0);        }}int bfs(){    int i, j, rear = 0;    memset(d, -1, sizeof(d[0]) * (T + 1));    d[S] = 0, q[rear ++] = S;    for(i = 0; i < rear; i ++)        for(j = first[q[i]]; j != -1; j = next[j])            if(flow[j] && d[v[j]] == -1)            {                d[v[j]] = d[q[i]] + 1, q[rear ++] = v[j];                if(v[j] == T) return 1;            }    return 0;}int dfs(int cur, int a){    if(cur == T) return a;    for(int &i = work[cur]; i != -1; i = next[i])        if(flow[i] && d[v[i]] == d[cur] + 1)            if(int t = dfs(v[i], std::min(a, flow[i])))            {                flow[i] -= t, flow[i ^ 1] += t;                return t;                }    return 0;}int dinic(){    int ans = 0, t;    while(bfs())    {        memcpy(work, first, sizeof(first[0]) * (T + 1));        while(t = dfs(S, INF))            ans += t;        }        return ans;}void solve(){    printf("%d\n", dinic());    }int main(){    while(scanf("%d%d", &M, &N) == 2)    {        init();        solve();    }    return 0;    }