解析

我大受震撼。
真的沒想到是網絡流。（事后諸葛：看幾百的數據范圍應該試試枚舉算法）
一道比較開眼界的題吧。
然而用一個十分鐘寫完的假做法可以騙90分，還是挺香的

首先是一個沒什么意思的轉化：操作等價于給一條邊權值加一。
設特殊邊為 $(u,v,w)$，想想什么時候這條邊會可能不在最小生成樹上。
不難發現，如果最終這條邊不在生成樹上，那么樹上 $(u,v)$ 路徑的所有邊必然權值都不大于 $w$。
所以存在一條從 u 到 v ，路上權值均不大于 w 的路徑是不符合要求的必要條件。
然后不難發現如果存在，也一定可以構造出不含要求邊的生成樹，所以它就充要了。
那么題意就變成了通過若干次加權，使得整張圖不存在一條從 u 到 v ，路上權值均不大于 w 的路徑。
可以用最小割解決。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=1550; const int inf=1e9; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,id;int s,t,tot; struct node{int to,nxt,cap; }p[N<<1]; int fi[N],cur[N],cnt; inline void Addline(int x,int y,int cap){p[++cnt]=(node){y,fi[x],cap};fi[x]=cnt; } inline void add(int x,int y,int c){Addline(x,y,c);Addline(y,x,0); } int bel[N]; int q[N],st,ed; int bfs(){memset(bel,0,sizeof(int)*(tot+1));bel[s]=1;q[st=ed=1]=s;while(st<=ed){int now=q[st++];for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap||bel[to]) continue;bel[to]=bel[now]+1;q[++ed]=to;}}return bel[t]; } int dfs(int x,int lim){if(x==t||!lim) return lim;int res(0);for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(bel[to]!=bel[x]+1) continue;int add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(!res) bel[x]=-1;return res; } int dinic(){int flow(0),tmp(0);while(bfs()){while((tmp=dfs(s,inf))) flow+=tmp;}return flow; }int u[N],v[N],w[N],val; signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();m=read();int id=read();tot=n;memset(fi,-1,sizeof(fi));cnt=-1;for(int i=1;i<=m;i++){u[i]=read(),v[i]=read();w[i]=read();if(id==i){val=w[i];s=u[i];t=v[i];}}for(int i=1;i<=m;i++){if(i==id) continue;int f=val-w[i]+1;if(f>0){add(u[i],v[i],f);add(v[i],u[i],f);}}printf("%d\n",dinic());return 0; }

總結

以上是生活随笔為你收集整理的P5039 [SHOI2010]最小生成树（网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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