P4897 【模板】最小割樹（Gomory-Hu Tree）
這個算法可以用來求解一個無向圖上任意兩點的最小割，具體過程就是每次選擇兩個點求最小割，然后在一個新圖中這兩個點連邊，然后對于這兩個點的連通塊分別遞歸處理，可以發現這樣得到的一定是一個樹，然后兩個點的最小割等于這兩個點在樹鏈上的邊權最小值，可以倍增求解。
具體證明：
https://www.cnblogs.com/birchtree/p/10761585.html
代碼細節：
記得無向圖網絡流建邊要雙向連，所以一共需要條邊，另外還要注意每一次重新求解要將流量數組還原，這里的最小割依然是整張圖上的，不是遞歸范圍的。
#include<bits/stdc++.h>
#define LL long long
#define V inline void
#define I inline int
#define FOR(i,a,b) for(register int i=a,end##i=b;i<=end##i;++i)
#define REP(i,a,b) for(register int i=a,end##i=b;i>=end##i;--i)
using namespace std
;
inline int read()
{char x
='\0';int fh
=1,sum
=0;for(x
=getchar();x
<'0'||x
>'9';x
=getchar())if(x
=='-')fh
=-1;for(;x
>='0'&&x
<='9';x
=getchar())sum
=sum
*10+x
-'0';return fh
*sum
;
}
const int N
=2009,M
=4009,INF
=0x3f3f3f3f;
int n
,m
,q
;
namespace netflow
{struct lian
{int to
,pre
,cap
;}e
[M
<<1];int hed
[N
],lcnt
=1;V
jlian(int x
,int y
,int cap
){e
[++lcnt
]={y
,hed
[x
],cap
};hed
[x
]=lcnt
;e
[++lcnt
]={x
,hed
[y
],0};hed
[y
]=lcnt
;}int cur
[N
],dep
[N
];queue
<int>q
;I
bfs(int S
,int T
){memcpy(cur
,hed
,sizeof(hed
));memset(dep
,0,sizeof(dep
));dep
[S
]=1,q
.push(S
);while(!q
.empty()){int now
=q
.front();q
.pop();for(int i
=hed
[now
];i
;i
=e
[i
].pre
){int to
=e
[i
].to
;if(e
[i
].cap
&&dep
[to
]==0){dep
[to
]=dep
[now
]+1;q
.push(to
);}}}return dep
[T
]!=0;}I
dfs(int now
,int T
,int flow
){if(now
==T
||flow
==0)return flow
;int res
=flow
;for(int &i
=cur
[now
];i
;i
=e
[i
].pre
){int to
=e
[i
].to
;if(e
[i
].cap
&&dep
[now
]+1==dep
[to
]){int k
=dfs(to
,T
,min(res
,e
[i
].cap
));e
[i
].cap
-=k
,e
[i
^1].cap
+=k
,res
-=k
;if(res
==0)break;}}return flow
-res
;}V
init(){for(int i
=2;i
<=lcnt
;i
+=2){e
[i
].cap
+=e
[i
^1].cap
;e
[i
^1].cap
=0;}}I
dinic(int S
,int T
){init();int maxflow
=0;while(bfs(S
,T
))maxflow
+=dfs(S
,T
,INF
);return maxflow
;}
}namespace mincut
{struct lian
{int to
,pre
,w
;}e
[N
<<1];int hed
[N
],lcnt
=1;inline void jlian(int x
,int y
,int w
){e
[++lcnt
]={y
,hed
[x
],w
};hed
[x
]=lcnt
;}int node
[N
],tmp1
[N
],tmp2
[N
];V
build(int lp
,int rp
){if(lp
==rp
)return;int s
=node
[lp
],t
=node
[lp
+1];
int ct
=netflow
::dinic(s
,t
);
jlian(s
,t
,ct
),jlian(t
,s
,ct
);int cnt1
=0,cnt2
=0;FOR(i
,lp
,rp
){if(netflow
::dep
[node
[i
]])tmp1
[++cnt1
]=node
[i
];else tmp2
[++cnt2
]=node
[i
];}int cnt
=lp
;FOR(i
,1,cnt1
)node
[cnt
++]=tmp1
[i
];FOR(i
,1,cnt2
)node
[cnt
++]=tmp2
[i
];build(lp
,lp
+cnt1
-1);build(lp
+cnt1
,rp
);}int dep
[N
],bz
[N
][11],mn
[N
][11];V
dfs(int x
,int fa
,int depth
){dep
[x
]=depth
,bz
[x
][0]=fa
;for(int i
=1;i
<=10;i
++){bz
[x
][i
]=bz
[bz
[x
][i
-1]][i
-1];mn
[x
][i
]=min(mn
[x
][i
-1],mn
[bz
[x
][i
-1]][i
-1]);}for(int i
=hed
[x
];i
;i
=e
[i
].pre
){int to
=e
[i
].to
;if(to
==fa
)continue;mn
[to
][0]=e
[i
].w
;dfs(to
,x
,depth
+1);}}V
solve(){memset(mn
,0x3f,sizeof(mn
));FOR(i
,1,n
)node
[i
]=i
;build(1,n
);dfs(1,0,1);}I
que(int x
,int y
){int ans
=0x3f3f3f3f;if(dep
[x
]<dep
[y
])swap(x
,y
);REP(i
,10,0){if(dep
[bz
[x
][i
]]>=dep
[y
])ans
=min(ans
,mn
[x
][i
]),x
=bz
[x
][i
];}if(x
==y
)return ans
;REP(i
,10,0){if(bz
[x
][i
]!=bz
[y
][i
]){ans
=min(ans
,mn
[x
][i
]);ans
=min(ans
,mn
[y
][i
]);x
=bz
[x
][i
],y
=bz
[y
][i
];}}ans
=min(ans
,mn
[x
][0]);ans
=min(ans
,mn
[y
][0]);return ans
;}
}int main()
{
n
=read()+1,m
=read();
FOR(i
,1,m
){int x
=read()+1,y
=read()+1,cap
=read();netflow
::jlian(x
,y
,cap
);netflow
::jlian(y
,x
,cap
);}
mincut
::solve();q
=read();FOR(i
,1,q
){int u
=read()+1,v
=read()+1;printf("%d\n",mincut
::que(u
,v
));}return 0;
}
總結
以上是生活随笔為你收集整理的P4897 【模板】最小割树（Gomory-Hu Tree）（网络流/最小割/树形结构）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
