题目大意

给出一个有$n$个点$m$条边的无向图

求至少要删掉几个点，使得新图存在两个点无法联通

数据范围

$0\leqslant n\leqslant 50$

题解

图的连通度问题是指：在图中删去部分元素(点或边)，使得图中指定的两个点s和t不连通(不存在从s到t的路径)，求至少要删去几个元素

图的连通度分为点连通度和边连通度：

1. 点连通度：只许删点，求至少要删掉几个点(当然，s和t不能删去，这里保证原图中至少有三个点)

2. 边连通度：只许删边，求至少要删掉几条边

并且，有向图和无向图的连通度求法不同，因此还要分开考虑(对于混合图，只需将其中所有的无向边按照无向图的办法处理、有向边按照有向图的办法处理即可)

【1】有向图的边连通度：

以$s$为源点，$t$为汇点建立网络，原图中的每条边在网络中仍存在，容量为$1$

求该网络的最小割(也就是最大流)的值即为原图的边连通度

【2】有向图的点连通度：

需要拆点来建立网络，原图中的每个点$i$在网络中拆成$i'$与$i''$，有一条边$i',i''$，容量为$1$

$(s',s'')$和$(t',t'')$例外，容量为正无穷

原图中的每条边$(i, j)$在网络中为边$(i'',j')$，容量为正无穷

以$s'$为源点、$t''$为汇点求最大流，最大流的值即为原图的点连通度

说明：显然，容量为正无穷的边不可能通过最小割，也就是原图中的边和$s、t$两个点不能删去；若边$(i,i'')$通过最小割，则表示将原图中的点i删去

【3】无向图的边连通度：

将图中的每条边$(i, j)$拆成$(i, j)$和$(j, i)$两条边，再按照有向图的办法【1】处理

【4】无向图的点连通度：

将图中的每条边$(i, j)$拆成$(i, j)$和$(j, i)$两条边，再按照有向图的办法【2】处理

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,S,T,ans,et;
struct edge{int to,next,c;}e[5050];
int last[105],d[105],q[105],u[5050],v[5050];
inline void addedge(int u,int v,int c){
    e[++et]=(edge){v,last[u],c};last[u]=et;
    e[++et]=(edge){u,last[v],0};last[v]=et;
}

inline void build(int s,int t){
    et=1;memset(last,0,sizeof(last));
    addedge(S,s,inf);addedge(t+n,T,inf);
    For(i,0,n-1)
        if (i!=s && i!=t) addedge(i,i+n,1);
        else addedge(i,i+n,inf);
    For(i,1,m){
        addedge(u[i]+n,v[i],inf);
        addedge(v[i]+n,u[i],inf);
    }
}

inline bool bfs(){
    memset(d,-1,sizeof(d));
    queue <int> q;q.push(S);d[S]=0;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h){
            if (d[e[i].to]==-1 && e[i].c){
                d[e[i].to]=d[h]+1;
                q.push(e[i].to);
            }
        }
    }
    return d[T]!=-1;
}

int dinic(int x,int flow){
    if (x==T) return flow;int a,used=0;
    goedge(i,x){
        if (d[e[i].to]==d[x]+1 && e[i].c){
            a=dinic(e[i].to,min(flow-used,e[i].c));
            e[i].c-=a,e[i^1].c+=a,used+=a;
            if (used==flow) return flow;
        }
    }
    if (!used) d[x]=-1;
    return used;
}

int main(){
    while (scanf("%d%d",&n,&m)!=EOF){
        S=2*n,T=2*n+1;
        For(i,1,m) u[i]=read(),v[i]=read();
        ans=n;
        For(i,0,n-1) For(j,i+1,n-1){
            build(i,j);
            int sum=0;
            while (bfs()) sum+=dinic(S,inf);
            ans=min(ans,sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

引用原文戳我