[SHOI2010]最小生成树

传送门

先说句闲话，好久没写题解了，主要是因为我的懒惰以及人类能鸽善鹉的本性。

但既然搭好了新blog，还是用一下吧，现在开始更新，不定时咕咕咕。

正题：

题意简述：

​ 给你一个无向图，你可以将除了你指定的一条边外的所有权值减一，每次代价为一。求对于指定的一条边，要花费多少代价使它一定成为最小生成树中的一条边。图的点数小于$500$，边数小于$800$。

做法：

​ 首先，将一个边以外的边全都减一，就相当于把它加一。

​ 第二，从$kruscal$ 的性质上考虑，如果一条边一定在最小生成树里，那么它所连接的两个点之间一定没有一条所包含的所有边都比它小的路径。因为最小生成树中不存在环，如果有环，那就要将环上最长的那条边删去。所以我们只要找到这种路径，将路径上最长的边加到比我们想要的边长，直到整个图中不存在这种路径即可。

​ 这样，我们规定的这条边就没有一种方案被其他边替代了。

实现：

​ 建立网络流模型，将图中所有边权不大于指定边权的边拿出来重新建图，边权改为与指定边权的差值加一，题目要求的边的两个端点分别为源点和汇点。那么我们上面所说的一条路径就是这个图中的一个流，目标状态是这个图中不存在流，跑一边最小割即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(int &x){scanf("%d",&x);}
#endif
using namespace std;
struct node{
    int next,to,z;
}w[5001];
int head[2001],cnt,deep[2001],ans,n,m,z,c,a,b;
int o[2001],tim,heap,tail,team[2001],cur[2001];
int f[2001],t[2001],l[2001],q;
inline void add(int x,int y,int z){
    w[cnt].next=head[x];
    w[cnt].to=y; w[cnt].z=z;
    head[x]=cnt; cnt++;
}
inline bool bfs(){
    for (int i=1; i<=n; i++) cur[i]=head[i];
    heap=tail=1; tim++; deep[a]=1;
    team[tail]=a; o[a]=tim;
    while (heap<=tail){
        int k=team[heap];
        for (int i=head[k]; i!=-1; i=w[i].next){
            if (o[w[i].to]!=tim&&w[i].z){
                deep[w[i].to]=deep[k]+1;
                o[w[i].to]=tim;
                team[++tail]=w[i].to;
            }
        }
        heap++;
    }
    return (o[b]==tim);
}
int dfs(int x,int v){
    if (x==b||v==0) return v;
    int used=0,minn,z;
    for (int &i=cur[x]; i!=-1; i=w[i].next){
        if (w[i].z&&deep[w[i].to]==deep[x]+1){
            minn=min(v-used,w[i].z);
            z=dfs(w[i].to,minn);
            if (z){
                w[i].z-=z; w[i^1].z+=z;
                used+=z;
            }
            if (used==v) break;
        }
    }
    if (!used) deep[x]=0;
    return used;
}
int main(){
    int x,y,z;
    read(n),read(m),read(q);
    for (int i=1; i<=m; i++){
        read(x),read(y),read(z);
        f[i]=x; t[i]=y; l[i]=z;
    }
    memset(head,-1,sizeof(head));
    a=f[q]; b=t[q]; c=l[q];
    for (int i=1; i<=m; i++){
        if (i==q) continue;
        if (l[i]<=c){
            add(f[i],t[i],c-l[i]+1);
//			printf("%d %d %d\n",f[i],t[i],c-l[i]+1);
            add(t[i],f[i],0);
            add(t[i],f[i],c-l[i]+1);
            add(f[i],t[i],0);
        }
    }
    while (bfs())
        ans+=dfs(a,1e9);
    printf("%d\n",ans);
    return 0;
}