题解 P5039 【[SHOI2010]最小生成树】

· · 题解

题意

给出一张图，问执行多少次

操作，可以使第\texttt{Lab}条边必然出现在这张图的最小生成树上

题解

看到题的第一秒：和[清华集训2012]最小生成树 好像啊

首先，根据相对运动的原理，我们知道，将其它边全部减小，就相当于将此边增大。因此，我们把整棵树的操作，改到了一条边上。

然后，我们考虑这么一张图：

选取\color{red}{\texttt{Lab}}的条件是什么？显然，

我们看一下题面：

使得标号为 Lab 边一定出现最小生成树中的最少操作次数。

因此，不能有一条从u_{Lab}到v_{Lab}的路径，使边权全部\leq d_{Lab}，因此我们可以将所有\leq d_{Lab}的边组成一张图，割去i的代价为d_{Lab}-d_i+1，跑一遍最小割即为正解

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;char c=getchar();bool f=false;
    for(;!isdigit(c);c=getchar())f!=c=='-';
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    if(f)x=-x;
}
template<typename T ,typename ...Arg>
inline void read(T &x,Arg &...args){
    read(x);read(args...);
}
template<typename T>
inline void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
const int maxn=4010,maxe=100010*2;
struct Graph{
    struct node{
        int v,w,nxt;
    }e[maxe<<1];
    int head[maxn],cur[maxn],tot;
    int dis[maxn];
    int s,t;
    void init(int _s,int _t){s=_s,t=_t;tot=1;memset(head,0,sizeof head);}
    Graph(int _s=0,int _t=0){init(_s,_t);}
    void add(int u,int v,int w){
        //printf("%d %d %d\n",u,v,w);
        e[++tot]=(node){v,w,head[u]},head[u]=tot;
        e[++tot]=(node){u,w,head[v]},head[v]=tot;
    }
    #define v e[i].v
    inline bool bfs(){
        queue<int>q;
        memset(dis,0,sizeof dis);
        memcpy(cur,head,sizeof head);
        dis[s]=1;q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt)
                if(!dis[v]&&e[i].w){
                    dis[v]=dis[u]+1,q.push(v);
                    if(v==t)return true;
                }
        }
        return  false;
    }
    int dfs(int u,int flow){
        if(u==t)return flow;
        int rest=flow;
        for(int i=cur[u];i&&rest;i=e[i].nxt){
            if(dis[v]==dis[u]+1&&e[i].w){
                int tmp=dfs(v,min(rest,e[i].w));
                rest-=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
            }
            cur[u]=i;
        }
        if(rest==0)dis[u]=-1;
        return flow-rest;
    }
    #undef v
    int dinic(){
        int ans=0;
        while(bfs())
            while(int sth=dfs(s,2e9))
                ans+=sth;
        return ans;
    }
}G;
int n,m,Lab;
int x[1000],y[1000],d[1000];
signed main(){
    read(n,m,Lab);
    for(int i=1;i<=m;i++)
        read(x[i],y[i],d[i]);
    G.init(x[Lab],y[Lab]);
    for(int i=1;i<=m;i++)
        if(i!=Lab&&d[i]<=d[Lab])
            G.add(x[i],y[i],d[Lab]-d[i]+1);
    write(G.dinic());
}