BZOJ1834[ZJOI2010]网络扩容——最小费用最大流+最大流

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。

求：

1、在不扩容的情况下，1到N的最大流；

2、将1到N的最大流增加K所需的最小扩容费用。

输入

第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。

接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

N<=1000，M<=5000，K<=10

输出

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

第一问没啥可说的，直接最大流就行。第二问显然是求最小费用最大流，第二次加边直接残量网络上把对应边建出来，不用再重新建图，只要把第一次建的边边权赋成INF，就能保证一定走的是第二次加的边。第二次加的边因为不确定每条边容量，所以都设成INF，但又要限制总流量，所以新建一个源点连一条边到原来的源点，容量为k，这样就保证了全图流量。

最后附上代码。

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

queue<int>Q;

int A[5010];

int B[5010];

int C[5010];

int D[5010];

int f[5010];

int vis[5010];

int c[100001];

int d[100001];

int q[100001];

int to[100001];

int val[100001];

int next[100001];

int from[100001];

int head[100001];

int S,T;

int sum;

int ans=0;

int tot=1;

int n,m,k;

int max_flow=0;

int INF=2147483647;

void add(int x,int y,int z,int w)

{

    tot++;

    next[tot]=head[x];

    head[x]=tot;

    to[tot]=y;

    c[tot]=z;

    val[tot]=w;

    from[tot]=x;

    tot++;

    next[tot]=head[y];

    head[y]=tot;

    to[tot]=x;

    c[tot]=0;

    val[tot]=-w;

    from[tot]=y;

}

int dfs(int x,int maxflow)

{

    if(x==T)

    {

        return maxflow;

    }

    int used=0;

    int nowflow;

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

    {

        if(c[i]!=0&&d[to[i]]==d[x]+1)

        {

            nowflow=dfs(to[i],min(maxflow-used,c[i]));

            c[i]-=nowflow;

            c[i^1]+=nowflow;

            used+=nowflow;

            if(nowflow==maxflow)

            {

                return maxflow;

            }

        }

    }

    if(used==0)

    {

        d[x]=-1;

    }

    return used;

}

bool bfs(int S,int T)

{

    memset(d,-1,sizeof(d));

    memset(q,0,sizeof(q));

    d[S]=0;

    int l=0;

    int r=0;

    q[r++]=S;

    while(l<r)

    {

        int now=q[l];

        for(int i=head[now];i;i=next[i])

        {

            if(d[to[i]]==-1&&c[i]!=0)

            {

                d[to[i]]=d[now]+1;

                q[r++]=to[i];

            }

        }

        l++;

    }

    if(d[T]!=-1)

    {

        return true;

    }

    return false;

}

void dinic()

{

    while(bfs(S,T)==true)

    {

        ans+=dfs(S,INF);

    }

}

bool SPFA()

{

    for(int i=0;i<=T;i++)

    {

        d[i]=INF;

    }

    d[S]=0;

    Q.push(S);

    vis[S]=1;

    while(!Q.empty())

    {

        int now=Q.front();

        Q.pop();

        vis[now]=0;

        for(int i=head[now];i;i=next[i])

        {

            if(!c[i])

            {

                continue;

            }

            if(d[to[i]]>d[now]+val[i])

            {

                d[to[i]]=d[now]+val[i];

                f[to[i]]=i;

                if(!vis[to[i]])

                {

                    Q.push(to[i]);

                    vis[to[i]]=1;

                }

            }

        }

    }

    return d[T]!=INF;

}

void result()

{

    int now=T;

    int flow=INF;

    while(now!=S)

    {

        flow=min(flow,c[f[now]]);

        now=from[f[now]];

    }

    max_flow+=flow;

    sum+=d[T]*flow;

    now=T;

    while(now!=S)

    {

        c[f[now]]-=flow;

        c[f[now]^1]+=flow;

        now=from[f[now]];

    }

}

void find_min()

{

    while(SPFA())

    {

        result();

    }

}

int main()

{

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

    S=1;

    T=n;

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

    {

        scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);

        add(A[i],B[i],C[i],0);

    }

    dinic();

    printf("%d ",ans);

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

    {

        add(A[i],B[i],INF,D[i]);

    }

    S=0;

    add(S,1,k,0);

    find_min();

    printf("%d",sum);

}

巴特西

BZOJ1834[ZJOI2010]网络扩容——最小费用最大流+最大流

题目描述

输入

输出

最新文章

热门文章