[BZOJ2521][Shoi2010]最小生成树（最小割）

2019-11-06 06:17:31

字体：大中小

来源：转载

供稿：网友

=== ===

这里放传送门

=== ===

题解

这题名字叫最小生成树实际上跟最小生成树的算法一点儿关系都没有。。当时学姐出胡策的时候ATP写了一个不科学到自己都懒得解释的东西结果骗到50pts。。人生成就达成。。。

考虑一条边权为W $W$ 的边(u,v) $(u,v)$ 如何会一定出现在最小生成树中，根据Kruskal的操作过程来看，如果所有小于等于W $W$ 的边都无法连通u $u$ 和v $v$ ，那么这条边就一定会被选入最小生成树中。对于这道题来说，操作可以等价为选择一条边然后把这条边的权值+1。显然进行操作的一定是边权小于等于W $W$ 的边，并且一定是直接把它修改成W+1 $W+1$ 不然没有用。那么对于每条边，设它原本的边权为val $val$ ，修改的代价就是W−val+1 $W-val+1$ 。

那么就转化成了这样一个问题：给出一个带边权的图，每次可以用一定的代价砍掉一条边，问使得两个给定的点不连通的最小花费。

显然的最小割问题了吧。。。。

代码

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int n,m,id,rec;struct edge{ int x,y,w,id;}e[810];int comp(edge a,edge b){return a.w<b.w;}namespace Mincut{ int p[510],tot,S,T,Maxflow,d[510],cur[510],N; struct edge{ int to,flw,nxt; }e[10010]; void in(int s,int t,int n){memset(p,-1,sizeof(p));S=s;T=t;N=n;} void add(int from,int to,int flow){ e[tot].to=to;e[tot].flw=flow;e[tot].nxt=p[from];p[from]=tot++; } bool Bfs(){ int q[1010],head,tail; memset(d,-1,sizeof(d)); head=0;tail=1; q[tail]=S;d[S]=0; for (int i=1;i<=n;i++) cur[i]=p[i]; while (head!=tail){ int u; head++;u=q[head]; for (int i=p[u];i!=-1;i=e[i].nxt){ int v=e[i].to; if (e[i].flw>0&&d[v]==-1){ d[v]=d[u]+1;tail++;q[tail]=v; } } } return d[T]!=-1; } int Dinic(int u,int Min){ if (u==T||Min==0) return Min; int r=0; for (int i=cur[u];i!=-1;i=e[i].nxt){ int v=e[i].to;cur[u]=i; if (e[i].flw>0&&d[v]==d[u]+1&&(r=Dinic(v,min(Min,e[i].flw)))){ e[i].flw-=r;e[i^1].flw+=r;return r; } } return 0; } int Deal(){ Maxflow=0; while (Bfs()){ int r=0; while (r=Dinic(S,0x7fffffff)) Maxflow+=r; } return Maxflow; }}int main(){ scanf("%d%d%d",&n,&m,&id); for (int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); e[i].id=i; } sort(e+1,e+m+1,comp); for (int i=1;i<=m;i++) if(e[i].id==id) rec=i; Mincut::in(e[rec].x,e[rec].y,n); for (int i=1;i<m;i++) if (e[i].w<=e[rec].w&&i!=rec){ Mincut::add(e[i].x,e[i].y,e[rec].w-e[i].w+1); Mincut::add(e[i].y,e[i].x,e[rec].w-e[i].w+1); } PRintf("%d/n",Mincut::Deal()); return 0;}