hdu 3549 Flow problem

红太狼 2021-12-09 15:41 178阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=3549][http_acm.hdu.edu.cn_showproblem.php_pid_3549]

题意分析：最大网络流 模板题

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    
    #define INF 0x7fffffff
    #define N 100
    
    using namespace std;
    
    int map[N][N],v[N];
    int pre[N];
    int n,m;
    
    int BFS(int s,int t)
    {
        queue<int>q;
        memset(pre,-1,sizeof(pre));
        memset(v,0,sizeof(v));
        pre[s] = s;
        v[s] = 1;
        q.push(s);
        int i;
        while(!q.empty())
        {
            int w = q.front();
            q.pop();
            for(i=1;i<=n;i++)
            {
                if(map[w][i]&&v[i] == 0)
                {
                    pre[i] = w;
                    v[i] = 1;
                    if(i == t)
                    {
                        return 1;
                    }
                    q.push(i);
                }
            }
        }
        return 0;
    }
    
    int EK(int s,int t)
    {
        int count = 0;
        int i,pp;
        while(BFS(s,t))
        {
            pp = INF;
            for(i=t;i!=s;i = pre[i])
            {
                if(pp>=map[pre[i]][i])
                {
                    pp = map[pre[i]][i];
                }
            }
            for(i=t;i!=s;i=pre[i])
            {
                map[pre[i]][i] -= pp;
                map[i][pre[i]] += pp;
            }
            count += pp;
        }
        return count;
    }
    
    int main()
    {
        int T,t=0,i,j;
        scanf("%d",&T);
        while(T--)
        {
            t++;
            int x,y,z;
            scanf("%d%d",&n,&m);
            memset(map,0,sizeof(map));
            while(m--)
            {
                scanf("%d%d%d",&x,&y,&z);
                map[x][y] += z;
            }
            printf("Case %d: %d\n",t,EK(1,n));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ACFLOOD/p/4302859.html

[http_acm.hdu.edu.cn_showproblem.php_pid_3549]: http://acm.hdu.edu.cn/showproblem.php?pid=3549