题意翻译

题目大意: 给定一个n(n <= 50)个点的无向图,求它的点联通度。即最少删除多少个点,使得图不连通。

解析

网络瘤拆点最小割。

定理

最大流\(=\)最小割

感性地理解(口胡)一下:首先显然最大流\(<=\)割,而根据最大流定义,最小割恰恰就是要恰好割断最大流经过的所有最窄流量的边集,就能恰好使得源点和汇点不连通,即最大流\(=\)最小割。

至于具体的证明,我也不知道。

拆点

一般来说,正常的拆点有两个作用:

  1. 在不改变原图连通性的情况下,将点权转化为边权。
  2. 通过化点为边,限制通过某点的流量。

对于无向图和有向图,一般意义上的拆点做法是相同的。

一般做法:以有向图为例,对于原图中的一个点对\((x,y)\),且有一条有向边\(c(x,y)\)。我们将其分别拆成两个点\(x,x',y,y'\),然后\(x\rightarrow x',y\rightarrow y'\)这样连接有向边,如果原来的点有点权那么将有向边的边权赋值为点权,如果没有点权则赋值为1。对于原图存在的有向边,连接\(x'\rightarrow y\)。

对于无向边,我们再连一条边\(y'\rightarrow x\)即可。

那么对于本题,显然是一个求最少割点,我们转化为拆点最大流做。

注意可能有多组数据。

参考代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define N 110
using namespace std;
struct node{
int next,ver,leng;
}g[N<<1];
int tot,head[N],d[N],n,m,a[N],b[N],s,t;
inline void add(int x,int y,int val)
{
g[++tot].ver=y,g[tot].leng=val;
g[tot].next=head[x],head[x]=tot;
}
inline bool bfs()
{
memset(d,0,sizeof(d));
queue<int> q;
d[s]=1;q.push(s);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=g[i].next){
int y=g[i].ver,z=g[i].leng;
if(!z||d[y]) continue;
d[y]=d[x]+1;
if(y==t) return 1;
q.push(y);
}
}
return 0;
}
inline int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow;
for(int i=head[x];i&&rest;i=g[i].next){
int y=g[i].ver,z=g[i].leng;
if(!z||d[y]!=d[x]+1) continue;
int k=dinic(y,min(rest,z));
if(!k) d[y]=0;
else{
g[i].leng-=k;
g[i^1].leng+=k;
rest-=k;
}
}
return flow-rest;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
int ans=INF;
for(int i=0;i<m;++i){
a[i]=b[i]=0;
char str[20];
scanf("%s",str);
int j=1;
while(str[j]!=',') a[i]=a[i]*10+str[j]-'0',++j;
j++;
while(str[j]!=')') b[i]=b[i]*10+str[j]-'0',++j;
}
for(s=0;s<n;++s)
for(t=0;t<n;++t){
if(s==t) continue;
memset(head,0,sizeof(head));
tot=1;
for(int i=0;i<n;++i)
if(i==s||i==t) add(i,i+n,INF),add(i+n,i,0);
else add(i,i+n,1),add(i+n,i,0);
for(int i=0;i<m;++i){
add(a[i]+n,b[i],INF),add(b[i]+n,a[i],INF);
add(b[i],a[i]+n,0),add(b[i],a[i]+n,0);
}
int now=0,tmp=0;
while(bfs())
while((now=dinic(s,INF))) tmp+=now;
ans=min(ans,tmp);
}
if(n<=1||ans==INF) ans=n;
cout<<ans<<endl;
}
return 0;
}
05-11 22:17