題目描述

　給定一個(gè)邊帶正權(quán)的連通無向圖G=(V,E)，其中N=|V|，M=|E|，N個(gè)點(diǎn)從1到N依次編號(hào)，給定三個(gè)正整數(shù)u，v，和L (u≠v)，假設(shè)現(xiàn)在加入一條邊權(quán)為L(zhǎng)的邊(u,v)，那么需要?jiǎng)h掉最少多少條邊，才能夠使得這條邊既可能出現(xiàn)在最小生成樹上，也可能出現(xiàn)在最大生成樹上？

輸入

第一行包含用空格隔開的兩個(gè)整數(shù)，分別為N和M；
接下來M行，每行包含三個(gè)正整數(shù)u，v和w表示圖G存在一條邊權(quán)為w的邊(u,v)。
最后一行包含用空格隔開的三個(gè)整數(shù)，分別為u，v，和 L；
數(shù)據(jù)保證圖中沒有自環(huán)。

輸出

輸出一行一個(gè)整數(shù)表示最少需要?jiǎng)h掉的邊的數(shù)量。

樣例輸入

3 2
3 2 1
1 2 3
1 2 2

樣例輸出

1

提示

對(duì)于20%的數(shù)據(jù)滿足N ≤ 10，M ≤ 20，L ≤ 20；

對(duì)于50%的數(shù)據(jù)滿足N ≤ 300，M ≤ 3000，L ≤ 200；

對(duì)于100%的數(shù)據(jù)滿足N ≤ 20000，M ≤ 200000，L ≤ 20000。

?

這道題和BZOJ2521差不多，只不過每條邊的流量都是$1$。因?yàn)榧纫笤谧钚∩蓸渲谐霈F(xiàn)又要求在最大生成樹中出現(xiàn)，所以只要兩種情況分別跑最小割然后答案加和即可。注意題目中要求給定邊可能出現(xiàn)，所以只將邊權(quán)嚴(yán)格小于/大于的邊加入到圖中即可。

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int head[30000]; int next[900000]; int to[900000]; int val[900000]; int tot=1; int n,m; int S,T; int ans; int x,y,z; int q[30000]; int d[30000]; int u[300000],v[300000],a[300000]; void add(int x,int y,int z) {next[++tot]=head[x];head[x]=tot;to[tot]=y;val[tot]=z;next[++tot]=head[y];head[y]=tot;to[tot]=x;val[tot]=0; } bool bfs(int S,int T) {memset(d,-1,sizeof(d));memset(q,0,sizeof(q));int l=0,r=0;q[r++]=S;d[S]=0;while(l<r){int now=q[l];l++;for(int i=head[now];i;i=next[i]){if(val[i]&&d[to[i]]==-1){d[to[i]]=d[now]+1;q[r++]=to[i];}}}return d[T]==-1?false:true; } int dfs(int x,int maxflow) {if(x==T){return maxflow;}int used=0;int nowflow;for(int i=head[x];i;i=next[i]){if(val[i]&&d[to[i]]==d[x]+1){nowflow=dfs(to[i],min(maxflow-used,val[i]));val[i]-=nowflow;val[i^1]+=nowflow;used+=nowflow;if(nowflow==maxflow){return maxflow;}}}if(used==0){d[x]=-1;}return used; } int dinic() {int res=0;while(bfs(S,T)){res+=dfs(S,0x3f3f3f3f);}return res; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&u[i],&v[i],&a[i]);}scanf("%d%d%d",&x,&y,&z);S=x,T=y;for(int i=1;i<=m;i++){if(a[i]<z){add(u[i],v[i],1);add(v[i],u[i],1);}}ans+=dinic();memset(head,0,sizeof(head));tot=1;for(int i=1;i<=m;i++){if(a[i]>z){add(u[i],v[i],1);add(v[i],u[i],1);}}ans+=dinic();printf("%d",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/10570400.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ2561最小生成树——最小割的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。