POJ1966.Cable TV Network——无向图的点连通度
http://poj.org/problem?id=1966
题目描述:
有线电视网络中,中继器的连接是双向的。如果网络中任何两个中继器之间至少有一条路,则中继器网络称为是连通的,否则中继器网络是不连通的。一个空的网络、以及只有一个中继器的网络被认为是连通的。具有n 个中继器的网络的安全系数f 被定义成:
(1) f 为n,如果不管删除多少个中继器,剩下的网络仍然是连通的;
(2) f 为删除最少的顶点数,使得剩下的网络不连通。
分析:
本题中的安全系数f 实际上就是无向图的顶点连通度κ(G)。
拆点建边 cap(u,u’)=1
(u,v)-> cap(u’,v)=inf,cap(v’,u)=inf
固定一个源点,枚举汇点,多次求解最大流
当maxflow=0,说明source与sink不连通
当maxflow=inf,说明source与sink相邻
否则,maxflow=p(source,sink) ,p(u,v)为独立轨的数目
//248K 16MS C++
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a,b) memset(a,b,sizeof(a))
#define min(a,b) (a<b?a:b)
const int MAXN = 110;
const int MAXM = 10010;
const int INF = 0x3f3f3f3f;
using namespace std;
int maze[MAXN][MAXN];
int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];
int flow[MAXN][MAXN];
int sap(int source,int sink,int N){
clr(cur,0);
clr(dis,0);
clr(gap,0);
clr(flow,0);
int u=pre[source]=source,maxflow=0,aug=-1;
gap[0]=N;
while(dis[source]<N){
int ok=0;
for(int v=cur[u];v<N;++v){
if(maze[u][v]-flow[u][v]&&dis[u]==dis[v]+1){
if(aug==-1||aug>maze[u][v]-flow[u][v])
aug=maze[u][v]-flow[u][v];
pre[v]=u;
u=cur[u]=v;
ok=1;
if(v==sink){
maxflow+=aug;
for(u=pre[u];v!=source;v=u,u=pre[u]){
flow[u][v]+=aug;
flow[v][u]-=aug;
}
aug=-1;
}
break;
}
}
if(ok) continue;
int mindis=N-1;
for(int v=0;v<N;++v){
if(maze[u][v]-flow[u][v]&&mindis>dis[v]){
cur[u]=v;
mindis=dis[v];
}
}
if((--gap[dis[u]])==0) break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.cpp","r",stdin);
#endif // ONLINE_JUDGE
int n,m,u,v;
while(scanf("%d%d",&n,&m)==2){
clr(maze,0);
rep(i,n) maze[i][i+n]=1;
rep(i,m){
scanf(" (%d,%d)",&u,&v);
maze[u+n][v]=INF;
maze[v+n][u]=INF;
}
int ans=INF;
rep1(i,1,n){
int tmp=sap(0+n,i,n<<1);
ans=min(ans,tmp);
}
if(ans==INF) printf("%d\n",n);
else printf("%d\n",ans);
}
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。