BZOJ-2521: [Shoi2010]最小生成树

Description

给你一张带有边权的无向图，你可以花费一代价使得除了一条边之外的所有边的边权-1，询问最小代价使得指定一条边一定出现在最小生成树上。1<=n<=500,1<=M<=800,1 <=D < 10^6

除了一条边其他边边权都-1相当于这条边边权+1，krustal算法的话，只有当所有<=指定边权的其他边不能使两端点联通时，该边一定在最小生成树上。一条边剔除的代价是边权之差+1，问题就转化为求一下这个图的最小割。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,id,s,t,ans;
struct edge
{
    int x,y,w;
}a[900];
int head[600],to[2100],f[2100],nxt[2100],cnt=1;
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int dis[600];
queue<int>q;
bool bfs()
{
    memset(dis,-1,sizeof dis);
    while(!q.empty()) q.pop();
    q.push(s); dis[s]=0; int x;
    while(!q.empty())
    {
        x=q.front(); q.pop();
        for(int i=head[x];i;i=nxt[i])
            if(f[i]>0&&dis[to[i]]==-1)
            {
                dis[to[i]]=dis[x]+1;
                if(to[i]==t) return true;
                q.push(to[i]);
            }
    }
    return false;
}
int dinic(int x,int flow)
{
    if(x==t) return flow;
    int xx,tmp=flow;
    for(int i=head[x];i;i=nxt[i])
        if(f[i]>0&&dis[to[i]]==dis[x]+1)
        {
            xx=dinic(to[i],min(f[i],tmp));
            if(!xx) dis[to[i]]=-1;
            f[i]-=xx; f[i^1]+=xx; tmp-=xx;
            if(!tmp) break;
        }
    return flow-tmp;
}
int main()
{
    scanf("%d%d%d",&n,&m,&id);
    for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
    for(int i=1;i<=m;++i) if(a[i].w<=a[id].w&&i!=id) add(a[i].x,a[i].y,a[id].w-a[i].w+1);
    s=a[id].x; t=a[id].y;
    while(bfs()) ans+=dinic(s,inf);
    printf("%d\n",ans);
    return 0;
}