首页 > 代码库 > 洛谷 P3381 【模板】最小费用最大流

洛谷 P3381 【模板】最小费用最大流

题目描述

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入输出格式

输入格式:

 

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。

 

输出格式:

 

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

 

输入输出样例

输入样例#1:
4 5 4 34 2 30 24 3 20 32 3 20 12 1 30 91 3 40 5
输出样例#1:
50 280

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=5000,M<=50000

样例说明:

技术分享

如图,最优方案如下:

第一条流为4-->3,流量为20,费用为3*20=60。

第二条流为4-->2-->3,流量为20,费用为(2+1)*20=60。

第三条流为4-->2-->1-->3,流量为10,费用为(2+9+5)*10=160。

故最大流量为50,在此状况下最小费用为60+60+160=280。

故输出50 280。

 

最小费用最大流 

妈的 交了15遍 !!

把最大流的bfs找增光路改成spfa找增光路。

屠龙宝刀点击就送

技术分享
#include <cstring>#include <cstdio>#define inf 0x7fffffff#define maxm 500005using namespace std;bool vis[maxm];int cost;int next[maxm],to[maxm],flow[maxm],price[maxm],from[maxm],fa[maxm],dis[maxm],head[maxm]; int answer,n,m,S,T,i,j,cnt=1;bool spfa(int s,int t){    for(i=1;i<=n;++i) {dis[i]=inf;fa[i]=-1;}    vis[s]=1;dis[s]=0;    int Q[maxm*10],l=0,r=1;    Q[r]=s;     while(l<r)    {        int tp=Q[++l];        for(i=head[tp];i;i=next[i])        {            int to_=to[i];            if(dis[to_]>dis[tp]+price[i]&&flow[i])            {                dis[to_]=dis[tp]+price[i];                fa[to_]=i;                if(!vis[to_])                {                    vis[to_]=1;                    Q[++r]=to_;                }            }        }        vis[tp]=0;    }    return dis[t]<inf;}int qr(int &x){    x=0;int f=1;char ch=getchar();    while(ch>9||ch<0)    ch=getchar();    while(ch>=0&&ch<=9)    {        x=x*10+(int)ch-48;        ch=getchar();    }}int main(){    qr(n);qr(m);qr(S);qr(T);     for(int u,v,w,f;m--;)    {        qr(u);qr(v);qr(w);qr(f);        next[++cnt]=head[u];        to[cnt]=v;        from[cnt]=u;        flow[cnt]=w;        price[cnt]=f;        head[u]=cnt++;    }    while(spfa(S,T))    {        int f=inf,now=T;        while(fa[now]!=-1)        {            if(flow[fa[now]]<f) f=flow[fa[now]];            now=from[fa[now]];        }        now=T;        while(fa[now]!=-1)        {            flow[fa[now]]-=f;            if(!to[fa[now]^1])            {                to[fa[now]^1]=from[fa[now]];                from[fa[now]^1]=to[fa[now]];                price[fa[now]^1]=-price[fa[now]];                next[fa[now]^1]=head[to[fa[now]]];                head[to[fa[now]]]=fa[now]^1;            }            flow[fa[now]^1]+=f;            now=from[fa[now]];        }        answer+=f;cost+=f*dis[T];    }    printf("%d %d",answer,cost);    return 0;}
AC代码
技术分享
#include <cstring>#include <cstdio>#include <queue>#define inf 0x7fffff#define Maxn 500000using namespace std;bool vis[Maxn];int cost,flow[Maxn],fa[Maxn],dis[Maxn],head[Maxn],answer,n,m,S,T,i,j,tot=1;struct node{    int next,to,value,price;}edge[Maxn*2];inline void add(int u,int v,int w,int f){    tot++;    edge[tot].next=head[u];    edge[tot].to=v;    edge[tot].value=w;    edge[tot].price=f;    head[u]=tot;}bool spfa(int s,int t){    queue<int>Q;    for(i=1;i<=n;++i) {dis[i]=inf;vis[i]=0;flow[i]=inf;}    vis[s]=1;    dis[s]=0;    fa[s]=0;    Q.push(s);     while(!Q.empty())    {        int tp=Q.front();Q.pop();        vis[tp]=0;        for(i=head[tp];i!=-1;i=edge[i].next )        {            int to=edge[i].to;            if(dis[to]>dis[tp]+edge[i].price&&edge[i].value)            {                dis[to]=dis[tp]+edge[i].price;                flow[to]=min(flow[tp],edge[i].value);                fa[to]=i;                if(!vis[to])                {                    vis[to]=1;                    Q.push(to) ;                }            }        }    }    return dis[t]<inf;}void Dinic(int s,int t){    while(spfa(s,t))    {        int f=flow[t];        for(int x=t;x!=s&&x!=-1;x=edge[fa[x]^1].to)        {            edge[fa[x]].value-=f;            edge[fa[x]^1].value+=f;        }        answer+=f;cost+=f*dis[t];    }}int qr(int &x){    x=0;int f=1;char ch=getchar();    while(ch>9||ch<0)    {        if(ch==-) f=-1;        ch=getchar();    }    while(ch>=0&&ch<=9)    {        x=x*10+(int)ch-48;        ch=getchar();    }    x*=f;}int main(){    memset(head,-1,sizeof(head));    qr(n);qr(m);qr(S);qr(T);     for(int u,v,w,f;m--;)    {        qr(u);qr(v);qr(w);qr(f);        add(u,v,w,f);        add(v,u,0,-f);    }    Dinic(S,T);    printf("%d %lld",answer,cost);    return 0;}
TLE代码 求优化

 

洛谷 P3381 【模板】最小费用最大流