1532.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 45 行

#include <stdio.h>
#include<string>
#define MAXN 210
#define inf 2110000000
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int n,m;
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
    int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
    if (source==sink) return inf;
    for (i=0;i<n;i++)
        for (j=0;j<n;flow[i][j++]=0);
    for (;;){
        for (i=0;i<n;pre[i++]=0);
        pre[t=source]=source+1,d[t]=inf;
        for (p=q=0;p<=q&&!pre[sink];t=que[p++])
            for (i=0;i<n;i++)
                if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
                    pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
                else if (!pre[i]&&(j=flow[i][t]))
                    pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
        if (!pre[sink]) break;
        for (i=sink;i!=source;)
            if (pre[i]>0)
                flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
            else
                flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
    }
    for (j=i=0;i<n;j+=flow[source][i++]);
    return j;
}
int main()
{
    while (scanf("%d%d",&m,&n)==2){
        int i;
        int f,t,c;
        memset(mat,0,sizeof(mat));
        for (i=0;i<m;i++){
            scanf("%d%d%d",&f,&t,&c);
            mat[f-1][t-1]+=c;
        }
        printf("%d\n",max_flow(n,mat,0,n-1,flow));
    }
    return 0;
}