洛谷 P2604 [ZJOI2010]网络扩容

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

输入输出格式

输入格式：

输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

13 19

说明

30%的数据中，N<=100

100%的数据中，N<=1000，M<=5000，K<=10

第一问任何费用为0,流量为给定流量的最大流

第二问源点到第一个点流量为k 其他流量为inf ,费用为给定费用的费用流

屠龙宝刀点击就送

#include <cstring>

#include <ctype.h>

#include <cstdio>

#include <queue>

#define M 50005

#define inf 0x7fffffff

using namespace std;

void read(int &x)

{

    x=;bool f=;

    register char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=;

    for(;isdigit(ch);ch=getchar()) x=x*+ch-'';

    x=f?(~x)+:x;

}

struct Edge

{

    int next,to,flow,value;

    Edge(int next=,int to=,int flow=,int value=) :next(next),to(to),flow(flow),value(value) {}

}edge[M<<];

bool vis[M<<];

int u[M],v[M],c[M],w[M],n,m,k,dep[M<<],dis[M<<],fa[M<<],flow[M<<],head[M<<],cnt=;

void insert(int u,int v,int w,int l)

{

    edge[++cnt]=Edge(head[u],v,w,l);

    head[u]=cnt;

}

bool bfs(int s,int t)

{

    memset(dep,-,sizeof(dep));

    dep[s]=;

    queue<int>Q;

    Q.push(s);

    while(!Q.empty())

    {

        int now=Q.front();

        Q.pop();

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

        {

            int v=edge[i].to;

            if(dep[v]==-&&edge[i].flow>)

            {

                dep[v]=dep[now]+;

                if(v==t) return true;

                Q.push(v);

            }

        }

    }

    return false;

}

int min(int a,int b) {return a>b?b:a;}

int dfs(int now,int t,int came_flow)

{

    if(now==t||came_flow==) return came_flow;

    int f,res=;

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

    {

        int v=edge[i].to;

        if(dep[v]==dep[now]+&&edge[i].flow>&&(f=dfs(v,t,min(came_flow,edge[i].flow))))

        {

            res+=f;

            came_flow-=f;

            edge[i].flow-=f;

            edge[i^].flow+=f;

            if(came_flow==) break;

        }

    }

    if(res!=came_flow) dep[now]=-;

    return res;

}

bool spfa(int s,int t)

{

    for(int i=s;i<=t;i++) {flow[i]=inf;dis[i]=inf;vis[i]=;}

    vis[s]=;

    fa[s]=;

    dis[s]=;

    queue<int>Q;

    Q.push(s);

    while(!Q.empty())

    {

        int now=Q.front();

        Q.pop();

        vis[now]=;

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

        {

            int v=edge[i].to;

            if(dis[v]>dis[now]+edge[i].value&&edge[i].flow>)

            {

                dis[v]=dis[now]+edge[i].value;

                flow[v]=min(flow[now],edge[i].flow);

                fa[v]=i;

                if(!vis[v])

                {

                    vis[v]=;

                    Q.push(v);

                }

            }

        }

    }

    return dis[t]<inf;

}

int update(int s,int t)

{

    int x=flow[t];

    for(int i=t;i!=s&&i;i=edge[fa[i]^].to)

    {

        edge[fa[i]].flow-=x;

        edge[fa[i]^].flow+=x;

    }

    return dis[t]*x;

}

int dinic(int s,int t,int type)

{

    int ans=;

    if(type==)

        for(;bfs(s,t);ans+=dfs(s,t,inf));

    else for(;spfa(s,t);ans+=update(s,t));

    return ans;

}

int main()

{

    read(n);

    read(m);

    read(k);

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

    {

        read(u[i]);

        read(v[i]);

        read(c[i]);

        read(w[i]);

        insert(u[i],v[i],c[i],);

        insert(v[i],u[i],,);

    }

    printf("%d ",dinic(,n,));

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

    {

        insert(u[i],v[i],inf,w[i]);

        insert(v[i],u[i],,-w[i]);

    }

    insert(,,k,);

    insert(,,,);

    printf("%d\n",dinic(,n,));

    return ;

}

巴特西

洛谷 P2604 [ZJOI2010]网络扩容

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章