[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); } 偏偏在最后出現的補充說明

最小生成樹有很多性質啊做題的時候多想一點