Description

给定一张N个点M条边的连通无向图，问最少需要断开多少条边使得这张图不再连通。

Input

第一行两个整数N,M含义如题所示。
接下来M行，每行两个正整数x,y，表示x和y之间有一条无向边。
输入数据保证连通性且无自环。

Output

输出最少需要断开多少条边。

Sample Input

5 7
1 2
2 3
3 4
4 5
5 1
2 4
1 3

Sample Output

2

Data Constraint

Solution

• 直接做 N−1 次最小割？

• 听说会超时……

• 于是我们用一种全新的方法——最小割树！

• 一开始所有点都在同一个集合中，随意取两点 s,t 为源、汇点做一遍最小割。

• 之后点就被割成了两个集合，即 s.t 所在的两个集合。

• 再对这两个集合分治递归下去，继续做最小割。

• 这样求出来的 N−1 个最小割中的最小值即为答案。

Code

#include<cstdio> #include<cstring> #include<cctype> using namespace std; const int N=305,M=N*15,inf=1e9; int n,m,tot=1,ans=inf,s,t; int first[N],nex[M],en[M],w[M]; int dis[N],gap[M],cur[N],a[N],b[N]; bool bz[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int min(int x,int y) {return x<y?x:y; } inline void ins(int x,int y,int z) {nex[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void insert(int x,int y) {ins(x,y,1),ins(y,x,1); } int sap(int x,int y) {if(x==t) return y;int use=0;for(int i=cur[x];i;i=nex[i])if(w[i] && dis[x]==dis[en[i]]+1){cur[x]=i;int num=sap(en[i],min(w[i],y-use));w[i]-=num,w[i^1]+=num,use+=num;if(use==y || dis[s]>m) return use;}cur[x]=first[x];if(!--gap[dis[x]]) dis[s]=m+1;gap[++dis[x]]++;return use; } void dfs(int x) {bz[x]=true;for(int i=first[x];i;i=nex[i])if(w[i] && !bz[en[i]]) dfs(en[i]); } void solve(int l,int r) {if(l==r) return;s=a[l],t=a[r];memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));for(int i=2;i<=tot;i+=2) w[i]=w[i^1]=w[i]+w[i^1]>>1;gap[0]=m;for(int i=1;i<=n;i++) cur[i]=first[i];int sum=0;while(dis[s]<=m) sum+=sap(s,inf);ans=min(ans,sum);memset(bz,false,sizeof(bz));dfs(s);int ll=l,rr=r;for(int i=l;i<=r;i++)if(bz[a[i]]) b[ll++]=a[i]; else b[rr--]=a[i];for(int i=l;i<=r;i++) a[i]=b[i];solve(l,ll-1);solve(ll,r); } int main() {n=read(),m=read();if(m==n-1) return 0&puts("1");for(int i=1;i<=m;i++) insert(read(),read());for(int i=1;i<=n;i++) a[i]=i;solve(1,n);printf("%d",ans);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5630. 【NOI2018模拟4.4】Connection的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。