UVA 1660 Cable TV Network

题意：

　　　求一个无向图的点连通度。

分析：

　　把一个点拆成一个入点和一个出点，之间连一条容量为1的有向边，表示能被用一次。最大流求最小割即可。套模板就好

代码;

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=110;
#define INF 1<<29
int g[maxn][maxn],flow[maxn][maxn];
int f[maxn];
int bfs(int n,int s,int e)
{

    int a[maxn];
    int u,v;
    memset(f,-1,sizeof(f));
    queue <int>q;
    memset(a,0,sizeof(a));
    q.push(s);
    a[s]=INF;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(v=0;v<n;v++)
        {
            if(!a[v]&&g[u][v]-flow[u][v]>0)
            {
                f[v]=u;
                a[v]=a[u]>g[u][v]-flow[u][v]?g[u][v]-flow[u][v]:a[u];
                q.push(v);
            }
        }
        if(u==e)
            break;
    }
    return a[e];
}
int EdmondsKarp(int n,int sp,int fp)
{
    int i,tmp;
    int maxflow=0;
    memset(flow,0,sizeof(flow));
    while(tmp=bfs(n,sp,fp))
    {
        for(i=fp;i!=sp;i=f[i])
        {
            flow[f[i]][i]+=tmp;
            flow[i][f[i]]-=tmp;
        }
        maxflow+=tmp;
    }
    return maxflow;
}
int main()
{
	int i,a,b;
	int n,m;
	while(~scanf("%d %d",&n,&m))
    {
		memset(g,0,sizeof(g));
		for(i=0;i<n;i++)
            g[i][i+n]=1;
		for(i=0;i<m;i++)
		{
			scanf(" (%d,%d)",&a,&b);
			g[a+n][b]=g[b+n][a]=INF;
		}
		int ans=INF;
		for(i=1;i<n;i++)
		{
			ans=min(ans,EdmondsKarp(n*2,n,i));
		}
		if(ans==INF)
            printf("%d\n",n);
		else
            printf("%d\n",ans);
	}
	return 0;
}

巴特西

UVA 1660 Cable TV Network

最新文章

热门文章