UVA1660 电视网络 Cable TV Network(最小割) UVA1660 电视网络 Cable TV Network(最小割)
题意：给定一个n(n <= 50)个点的无向图，求它的点联通度。即最少删除多少个点，使得图不连通。
题解：
关键思想枚举S，T。
当图不连通时，图中只要存在任意两点，使得S无法到T即可。
考虑如何建图，经典删点操作，将点拆点，把点转成边，流量为1，点间边流量为inf。
所有点对中，最小的最小割就是答案。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=107;
const int M=10007;
const int inf=1e9;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],tot;
int d[N],cur[N];
void add(int u,int v,int z){
e[tot]=v;
f[tot]=z;
ne[tot]=h[u];
h[u]=tot++;
e[tot]=u;
f[tot]=0;
ne[tot]=h[v];
h[v]=tot++;
}
void init(){
memset(h,-1,sizeof(h));
tot=0;
}
bool bfs(){
memset(d,-1,sizeof(d));
queue<int>sa;
d[S]=0;
cur[S]=h[S];
sa.push(S);
while(!sa.empty()){
int p=sa.front();
sa.pop();
for(int i=h[p];~i;i=ne[i]){
int to=e[i];
if(d[to]==-1&&f[i]>0){
d[to]=d[p]+1;
cur[to]=h[to];
if(to==T)return true;
sa.push(to);
}
}
}
return false;
}
int dfs(int p,int now){
if(p==T)return now;
int sum=0;
for(int i=cur[p];~i&&now>sum;i=ne[i]){
cur[p]=i;
int to=e[i];
if(d[to]==d[p]+1&&f[i]>0){
int lin=dfs(to,min(f[i],now-sum));
if(lin==0){
d[to]=-1;
}
else{
f[i]-=lin;
f[i^1]+=lin;
sum+=lin;
}
}
}
return sum;
}
int dinic(){
int res=0;
while(bfs()){
res+=dfs(S,inf);
}
return res;
}
int gao(int s,int t){
S=s+n;
T=t;
for(int i=0;i<tot;i+=2){
int u=e[i^1];
int v=e[i];
if(u+n==v){
f[i]=1;
f[i^1]=0;
}
else{
f[i]=inf;
f[i^1]=0;
}
}
int res=dinic();
return res;
}
int main(){
while(~scanf("%d %d",&n,&m)){
init();
for(int i=0;i<n;i++){
add(i,i+n,1);
}
for(int i=1;i<=m;i++){
int u,v;
scanf(" (%d,%d)",&u,&v);
add(u+n,v,inf);
add(v+n,u,inf);
}
int ans=n;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ans=min(ans,gao(i,j));
}
}
printf("%d
",ans);
}
}