【bzoj2521】【SHOI2010】【最小生成树】【最小割】

当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 P1P2，再把图中除了这条边以外的边，每一条的权值都减少1。如图 4所示就是一次这样的操作：

输出文件只有一行，这行只有一个整数，即，使得标号为Lab边一定出现最小生成树中的最少操作次数。

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D<10^6

题解:

   考虑一条边一定在最小生成树中意味着去掉这条边之后,权值小于等于它的边不能使这条边的两端点联通

   固定一条边不变把剩下的边都减一可以看成把这条边加一.

   那割掉一条边的代价就是v[x]-v[i]+1;

   然后直接最小割即可.

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2010
#define M 100010
#define inf 210000000 
using namespace std;
int point[N],next[M<<1],x,y,v,n,m,S,T,V,cnt=1;
int cur[N],dis[N],pre[N],gap[N],pos;
struct use{int st,en,v,id;
}e[M<<1],b[M];
void add(int x,int y,int v){//cout<<x<<' '<<y<<' '<<v<<endl; next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;next[++cnt]=point[y];point[y]=cnt;e[cnt].st=y;e[cnt].en=x;e[cnt].v=v;
}
int read(){int x(0);char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;
} 
bool cmp(use a,use b){return a.v<b.v;
}
int isap(int ss,int tt){int i,ans(0),mn,u=ss;gap[0]=n;for (i=1;i<=n;i++) cur[i]=point[i];while (dis[ss]<n){bool f=false;for (i=cur[u];i;i=next[i])if (dis[e[i].en]+1==dis[u]&&e[i].v){f=true;cur[u]=i;break;}if (f){pre[u=e[i].en]=i;if (u==tt){mn=inf;for (i=tt;i!=ss;i=e[pre[i]].st) mn=min(mn,e[pre[i]].v);ans+=mn;for (i=tt;i!=ss;i=e[pre[i]].st) e[pre[i]].v-=mn,e[pre[i]^1].v+=mn;u=ss;}}else{--gap[dis[u]];if (!gap[dis[u]]) return ans;for (mn=n,i=point[u];i;i=next[i]) if (e[i].v) mn=min(mn,dis[e[i].en]);gap[dis[u]=mn+1]++;cur[u]=point[u];if (u!=ss) u=e[pre[u]].st; } }return ans;
}
int main(){//freopen("a.in","r",stdin);n=read();m=read();pos=read();for (int i=1;i<=m;i++){x=read();y=read();v=read();b[i].st=x;b[i].en=y;b[i].v=v;b[i].id=i;if (i==pos) S=x,T=y,V=v; } sort(b+1,b+m+1,cmp);for (int i=1;i<=m;i++){if (b[i].v>V) break;if (b[i].id==pos) continue;add(b[i].st,b[i].en,V-b[i].v+1);}cout<<isap(S,T);
}