最大流裸题——pku1273

http://poj.org/problem?id=1273

人生第一题网络流O(∩_∩)O哈哈~

注意数据有重边，要把值加上去

#include<stdio.h>

const int inf=1000000000;
const int MAXN=209;
int map[MAXN][MAXN];
int flow[MAXN][MAXN];

int max_flow(int n,int mat[][MAXN],int source,int sink)
{
    int v[MAXN],c[MAXN],p[MAXN],ret=0,i,j;
    for(;;){
        for(i=0;i<n;i++)
            v[i]=c[i]=0;
        for(c[source]=inf;;){
            for(j=-1,i=0;i<n;i++)
                if(!v[i]&&c[i]&&(j==-1||c[i]>c[j]))
                    j=i;
            if(j<0)return ret;
            if(j==sink)break;
            for(v[j]=1,i=0;i<n;i++)
                if(mat[j][i]>c[i]&&c[j]>c[i])
                    c[i]=mat[j][i]<c[j]?mat[j][i]:c[j],p[i]=j;
        }
        for(ret+=j=c[i=sink];i!=source;i=p[i])
            mat[p[i]][i]-=j,mat[i][p[i]]+=j;
    }
    return ret;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;

        for(i=0;i<=m;i++)
        {
            for(j=0;j<=m;j++)
            {
                map[i][j]=0;
            }
        }
        int a,b,v;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&v);
            map[a-1][b-1]+=v;
        }
        int ret=max_flow(m,map,0,m-1);
        printf("%d\n",ret);
    }
}

PS：今天上了八节课，课堂上太无聊，所以看了看图论的网络流，还是比较容易理解的