网络流（EK算法）

poj1273
#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

const int maxn = 205;

ll n,m;

ll G[maxn][maxn];

ll pre[maxn];  //记录路径

bool flag[maxn];

bool bfs(ll be,ll en)

{

    queue<ll> q;

    mem(pre,-1);

    mem(flag,0);

    q.push(be);

    flag[be]=1;

    pre[be]=be;

    while(!q.empty())

    {

        ll front=q.front();

        q.pop();

        if(front==en)

            return 1;

        for(ll i=1;i<=n;i++)

        {

            if(!flag[i] && G[front][i]>0)  //没有被标记并且可行流大于0

            {

                flag[i]=1;

                pre[i]=front;

                q.push(i);

            }

        }

    }

    return 0;

}

ll EK(ll be,ll en)

{

    ll sum=0,mi;

    while(bfs(be,en))    //找一条增广路径

    {

        mi=0x3f3f3f3f;

        for(ll i=en;i!=be;i=pre[i])  //找最小边

        {

            mi=min(mi,G[pre[i]][i]);

        }

        for(ll i=en;i!=be;i=pre[i])

        {

            G[pre[i]][i]-=mi;  //更新正向

            G[i][pre[i]]+=mi;  //更新反向

        }

        sum+=mi;

    }

    return sum;

}

int main()

{

    while (scanf("%lld%lld",&m,&n)!=EOF)

    {

        mem(G,0);

        ll x,y,z;

        for(ll i=1;i<=m;i++)

        {

            scanf("%lld%lld%lld",&x,&y,&z);

            G[x][y]+=z;

        }

        printf("%lld\n",EK(1,n));

    }

    return 0;

}
巴特西

网络流（EK算法）

最新文章

热门文章
