BZOJ_2561_最小生成树

BZOJ_2561_最小生成树_最小割

题意：　给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？

分析：

如果所有边中有能使u，v连通且权值比L小的，那新加的这条边就不会出现在最小生成树上，最大生成树同理，那么问题就转化成求u，v之间的最小割，最小和最大分别做一次，相加即可。

注意无向图连边时容量。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

using namespace std;

#define N 20020

#define M 400050

#define inf 100000000

struct A

{

    int a,b,v;

}e[M];

int S,T,ans;

int head[N],to[M],nxt[M],cnt=1,flow[M],n,m;

int dep[N];

void add(int u,int v,int f)

{

    to[++cnt]=v;

    nxt[cnt]=head[u];

    head[u]=cnt;

    flow[cnt]=f;

}

bool bfs()

{

    queue <int> q;

    memset(dep,0,sizeof(dep));

    dep[S]=1;q.push(S);

    while(!q.empty())

    {

        int x=q.front();q.pop();

        for(int i=head[x];i;i=nxt[i])

        {

            if(!dep[to[i]]&&flow[i])

            {

                dep[to[i]]=dep[x]+1;

                if(to[i]==T)return 1;

                q.push(to[i]);

            }

        }

    }

    return 0;

}

int dfs(int x,int mf)

{

    if(x==T)return mf;

    int nf=0;

    for(int i=head[x];i;i=nxt[i])

    {

        if(dep[to[i]]==dep[x]+1&&flow[i])

        {

            int tmp=dfs(to[i],min(flow[i],mf-nf));

            nf+=tmp;

            flow[i]-=tmp;

            flow[i^1]+=tmp;

            if(nf==mf)break;

        }

    }

    dep[x]=0;

    return nf;

}

int dinic()

{

    int f,sum=0;

    while(bfs())

    {

        while(f=dfs(S,inf))

        {

            sum+=f;

        }

    }

    return sum;

}

int main()

{

    scanf("%d%d",&n,&m);

    int x,y,z;

    for(int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);

    }

    scanf("%d%d%d",&S,&T,&z);

    for(int i=1;i<=m;i++)

    {

        if(e[i].v<z)

        {

            add(e[i].a,e[i].b,1);

            add(e[i].b,e[i].a,1);

        }

    }

    ans+=dinic();

    memset(head,0,sizeof(head));

    cnt=1;

    for(int i=1;i<=m;i++)

    {

        if(e[i].v>z)

        {

            add(e[i].a,e[i].b,1);

            add(e[i].b,e[i].a,1);

        }

    }

    printf("%d",ans+dinic());

}

巴特西

BZOJ_2561_最小生成树_最小割

最新文章

热门文章