傳送門

Description

給定一個\(n\)個點\(m\)條邊的無向連通圖，多次詢問兩點之間的最小割

兩點間的最小割是這樣定義的：原圖的每條邊有一個割斷它的代價，你需要用最小的代價使得這兩個點不連通

Solution

對于一張無向圖，如果 \(s \rightarrow t\) 的最大流是 \(f\)，\(s\), \(t\) 所在的割集為 \(S\), \(T\)，那么 \(\forall_{x \in S, y \in T}\), \(\operatorname{maxflow}(x \rightarrow y) = f\)

根據以上性質，我們考慮遞歸求解

構造集合 \(G\) 的最小割樹：

• 任意選兩個點，求出最小割，在兩個點之間連權值為最小割的邊
• 對兩個割集分別求解

\(Wa\)了數十次

以后用static的時候還是注意點

Code?

#include<bits/stdc++.h> #define ll long long #define reg register #define ri reg int i using namespace std;inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; }const int MN=505,MM=1505,inf=1e9;struct edge{int to,w,nex;}e[MM<<1],E[MN<<1];int cur[MN],Hr[MN],hr[MN],En=1,en=1; void ins(int x,int y,int w,int *h,edge *ed,int &tt) {ed[++tt]=(edge){y,w,h[x]},h[x]=tt;ed[++tt]=(edge){x,w,h[y]},h[y]=tt; }int d[MN],q[MN],top;bool bfs(int S,int T) {memset(d,0,sizeof d);reg int i,j;for(d[q[i=top=1]=S]=1;i<=top;++i)for(j=hr[q[i]];j;j=e[j].nex)if(e[j].w&&!d[e[j].to])d[q[++top]=e[j].to]=d[q[i]]+1;return d[T]; }int dfs(int x,int T,int f) {if(x==T) return f;int used=0;for(int &i=cur[x];i;i=e[i].nex)if(e[i].w&&d[e[i].to]==d[x]+1){int tmp=dfs(e[i].to,T,min(f-used,e[i].w));e[i].w-=tmp,e[i^1].w+=tmp;used+=tmp;if(f==used) return f;}return d[x]=-1,used; }void clear(){for(reg int i=2;i<en;i+=2)e[i].w=e[i^1].w=(e[i].w+e[i^1].w)>>1;}int dinic(int S,int T) {int maxflow=0;clear();while(bfs(S,T)){memcpy(cur,hr,sizeof cur);maxflow+=dfs(S,T,inf);}return maxflow; }void Build(int *id, int n) {if(n==1) return;static int s[MN],t[MN];int cnts=0,cntt=0;int cut=dinic(id[0],id[1]);ins(id[0],id[1],cut,Hr,E,En);for(reg int i=0;i<n;++i)if(d[id[i]]) s[cnts++]=id[i];else t[cntt++]=id[i];memcpy(id,s,cnts<<2);memcpy(id+cnts,t,cntt<<2);if(cnts) Build(id,cnts);if(cntt) Build(id+cnts,cntt); }int n,dep[MN],fa[MN][15],path[MN][15];void init_dfs(int x,int f) {for(ri=Hr[x];i;i=E[i].nex)if(E[i].to!=f)dep[E[i].to]=dep[x]+1,fa[E[i].to][0]=x,path[E[i].to][0]=E[i].w,init_dfs(E[i].to,x); }void init() {dep[1]=1;init_dfs(1,-1);reg int i,j;for(i=1;i<10;++i)for(j=1;j<=n;++j){fa[j][i]=fa[fa[j][i-1]][i-1];path[j][i]=min(path[j][i-1],path[fa[j][i-1]][i-1]);} }int Min(int x,int y) {reg int ret=1e9;if(dep[x]>dep[y]) std::swap(x,y);reg int i,c=dep[y]-dep[x];for(i=8;~i;--i) if(c>>i&1){ret=min(ret,path[y][i]),y=fa[y][i]; }if(x==y) return ret;if(dep[x]!=dep[y]) return -1;for(i=8;~i;--i)if(fa[x][i]!=fa[y][i]){ret=min(ret,min(path[x][i],path[y][i])),x=fa[x][i],y=fa[y][i];}return min(ret,min(path[x][0],path[y][0])); }int id[MN]; int main() {reg int i,m,q,x,y;n=read(),m=read();while(m--) x=read(),y=read(),ins(x,y,read(),hr,e,en);for(i=1;i<=n;++i) id[i-1]=i;Build(id,n);init();q=read();while(q--){x=read();y=read();printf("%d\n",Min(x,y));}return 0; }

---

Blog來自PaperCloud，未經允許，請勿轉載，TKS！

轉載于:https://www.cnblogs.com/PaperCloud/p/10674424.html

總結

以上是生活随笔為你收集整理的【模板】最小割树（Gomory-Hu Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。