NYOJ677 EK算法求解最大流

题目大意：中文题。。。

算法思路：这里明显是求最小割的。那么什么是最小割呢？最小割就是所有割的权值之和的最小值，那么什么是割呢？割就是如果把图中的一条边或几条边去掉之后使得图变得不连通。这里可以用一个叫做最大流最小割的定理：在任意一个只有一个源和一个汇的图来说，最小割就等于最大流。因此可以把问题转化为求最大流的问题。这里用ek算法求解最大流。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 205
#define INF 0xfffffff
int t;
int n,m,p,a1,a2,a,b,src,sink;
int maps[MAXN][MAXN],pre[MAXN];
queue<int>que;
bool bfs(int s,int des)
{

    memset(pre,-1,sizeof(pre));
    while(!que.empty())
        que.pop();
    pre[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int index=que.front();
        que.pop();
        for(int i=s;i<=des;i++)
        {
            if(pre[i]==-1&&maps[index][i]>0)
            {
                pre[i]=index;
                if(i==des)
                    return true;
                que.push(i);
            }



        }


    }
    return false;
}
int MaxFlow(int s,int des)
{
    int maxflow=0;
    while(bfs(s,des))
    {
        int minflow=INF;
        for(int i=des;i!=s;i=pre[i])
            minflow=min(minflow,maps[pre[i]][i]);
        for(int i=des;i!=s;i=pre[i])
        {
            maps[pre[i]][i]-=minflow;
            maps[i][pre[i]]+=minflow;
        }
        maxflow+=minflow;
    }
    return maxflow;
}
int main()
{

    scanf("%d",&t);
    int sym=0;
    while(t--)
    {
        memset(maps,0,sizeof(maps));
        sym++;
        scanf("%d%d%d",&n,&m,&p);
        src=0;sink=n;
        for(int i=1;i<=p;i++)
        {
            scanf("%d",&a1);
            maps[src][a1]=maps[a1][src]=INF;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            maps[a][b]=maps[b][a]=1;
        }

        printf("Case #%d: %d\n",sym,MaxFlow(src,sink));

    }

    return 0;
}