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;
}
上一篇:JavaScript精要


下一篇:Day4 - Python基础4 迭代器、装饰器、软件开发规范