2017 ACM网络赛Smallest Minimum Cut(最小割的可行边或思维)

Smallest Minimum Cut

先说说正解

$假设每条边的流量都是1,那么最小割=割的边数$

$现在就是利用这个结论来找最小割的边数$

$假设一开始的最大流是maxflow$

$我把所有边的流量扩大x倍,嗯,最大流是x\ast maxflow$

$emm,这好像没有什么用$

$但是如果把所有边流量扩大x再加上1$

$设选了y条边作为割边,最大流就是x\ast maxflow+y$

$因为程序肯定选择最划算的,所以y一定最小。$

值得一提的是,x的选择是有讲究的

$因为求出最大流模x就是答案y$

$所以x一定要比maxflow大!!不然模的就是maxflow了!!$

$x取n+1比较保险$

---

再说说非正解

$至于为什么是非正解,我也不明白,网上的大神门说的...$

$因为跑一边最大流后,可以判断有些边是最小割的可行边$

$所以不是最小割的可行边的边把流量设置为inf,代表不会被割掉$

$可行边流量设置为1$

$这样跑最大流就是边数$

#include <bits/stdc++.h> using namespace std; const int maxn=2009; const int inf=1e9; int t,n,m,s; struct edge{ int u,to,nxt,flow; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int flow){ d[++cnt]=(edge){u,v,head[u],flow},head[u]=cnt; d[++cnt]=(edge){v,u,head[v],0},head[v]=cnt; } int dis[maxn]; bool bfs(int s,int t) { for(int i=0;i<=n;i++) dis[i]=0; queue<int>q; q.push(s); dis[s]=1; while( !q.empty() ) { int u=q.front(); q.pop(); for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( d[i].flow&&dis[v]==0 ) { dis[v]=dis[u]+1; if( v==t ) return true; q.push(v); } } } return false; } int dinic(int u,int t,int flow) { if( u==t ) return flow; int res=flow; for(int i=head[u];i&&res;i=d[i].nxt) { int v=d[i].to; if( d[i].flow&&dis[v]==dis[u]+1 ) { int temp=dinic(v,t,min(d[i].flow,res) ); if( temp==0 ) dis[v]=0; res-=temp; d[i].flow-=temp,d[i^1].flow+=temp; } } return flow-res; } int vis[maxn]; int main() { int T;cin >> T; while( T-- ) { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int l,r,flow; scanf("%d%d%d",&l,&r,&flow); add(l,r,flow); } int ans=0; while( bfs(s,t) ) ans+=dinic(s,t,inf); for(int i=2;i<=cnt;i+=2) { if( bfs(d[i].u,d[i].to) ) continue; else vis[i]=1; } for(int i=2;i<=cnt;i+=2) { if( vis[i] ) d[i].flow=1,d[i^1].flow=0; else d[i].flow=inf,d[i^1].flow=0; } int num=0; while( bfs(s,t) ) num+=dinic(s,t,inf); printf("%d\n",num); for(int i=2;i<=cnt;i++) vis[i]=0; for(int i=1;i<=n;i++) head[i]=0; cnt=1; } }