题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2521
题意：每次操作可以选择一条边权值不变，别的权值都减一，问使得某边成为最小生成树的必须边至少要几次操作。
首先有个显然的转化，别的都减一相当于选择一条边权值加一，会方便考虑。
考虑最小生成树的构建过程，一条边是必须边当且仅当只有它能联通两端点所在联通块。那么我们删掉这条边，使得得到的新图，两端点不连通即可。
就是显然的最小割模型了... 考虑到一条边能对我们选定的边构成“竞争”关系当且仅当这条边权值小于等于选定边，设选定边为 L，那么就可以重新构图，对于满足\(w_i<w_L\) 的边，连一条权值为\(w_L-w_i+1\) 的边即可
居然 1A..
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 510 #define M 810 #define ll long long #define inf 1000000000 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*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to,val; }edge[M<<1]; int cnt=1,head[N]; void add(int from,int to,int val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } void ins(int from,int to,int val) {add(from,to,val),add(to,from,val);} int n,m,L,S,T; int u[M],v[M],w[M]; int ans,d[N]; queue<int> q; bool bfs() { memset(d,0,sizeof(d)); d[S]=1;q.push(S); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(!d[to]&&val) { d[to]=d[x]+1; q.push(to); } } } return d[T]; } int dfs(int x,int v) { if(x==T||!v)return v; int ret=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to,val=edge[i].val; if(d[to]==d[x]+1) { int f=dfs(to,min(v,val)); edge[i].val-=f,edge[i^1].val+=f; v-=f,ret+=f; if(!v)break; } } if(!ret)d[x]=-1; return ret; } int main() { n=read(),m=read(),L=read(); for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),w[i]=read(); for(int i=1;i<=m;i++) { if(i==L)continue ; if(w[i]<=w[L]) ins(u[i],v[i],w[L]-w[i]+1); } S=u[L],T=v[L]; while(bfs())ans+=dfs(S,inf); printf("%d\n",ans); } |
Comments | NOTHING