Cogs 13. 运输问题4(费用流)

运输问题4

★★☆ 输入文件：maxflowd.in 输出文件：maxflowd.out 简单对比

时间限制：1 s 内存限制：128 MB

【问题描述】

一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。公路设有收费站，每通过一辆车，要交纳过路费。请你计算，在不考虑其它车辆使用公路的前提下，如何使产地运输到销地的商品最多，并使费用最少。

【输入格式】

输入文件有若干行

第一行，一个整数n，表示共有n个城市(2<=n<=100)，产地是1号城市，销地是n号城市

第二行，一个整数，表示起点城市

第三行，一个整数，表示终点城市

下面有n行,每行有2n个数字。第p行第2q−1,2q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且这两个数字分别表示该公路流量和每车费用。

【输出格式】

输出文件有一行

第一行，1个整数n，表示最小费用为n。

【输入输出样例】

输入文件名： maxflowd.in

6

1

6

0 0 1 3 5 10 0 0 0 0 0 0

0 0 0 0 0 0 5 7 0 0 0 0

0 0 0 0 0 0 0 0 2 8 0 0

0 0 0 0 1 3 0 0 0 0 3 5

0 0 2 4 0 0 0 0 0 0 2 6

0 0 0 0 0 0 0 0 0 0 0 0

输出文件名：maxflowd.out

63

/*

spfa连续最短路增广.

大概就是spfa跑一个最小费用然后不断调节流量.

用类似dinic的方法不断找增广费用路径.

*/

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 110

#define INF 1e9

using namespace std;

int n,m,S,T,cut=1,head[MAXN],fa[MAXN],ans,dis[MAXN],b[MAXN];

struct data{int u,v,next,f,c;}e[MAXN*MAXN];

queue<int>q;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

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

{

    e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].f=f;e[cut].next=head[u];head[u]=cut;

    e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].f=-f;e[cut].next=head[v];head[v]=cut;

}

bool bfs(int t)

{

    q.push(S);

    for(int i=0;i<=n;i++) dis[i]=INF;dis[S]=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();b[u]=0;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]>dis[u]+e[i].f&&e[i].c)

            {

                dis[v]=dis[u]+e[i].f;fa[v]=i;

                if(b[v]!=t) b[v]=t,q.push(v);

            }

        }

    }

    return dis[T]!=INF;

}

void mincost()

{

    int t=1;

    while(bfs(t))

    {

        int tmp=fa[T],x=INF;

        while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u];

        tmp=fa[T];

        while(tmp)

        {

            e[tmp].c-=x;

            e[tmp^1].c+=x;

            tmp=fa[e[tmp].u];

        }

        ans+=dis[T]*x;

        t++;

    }

    return ;

}

int main()

{

    freopen("maxflowd.in","r",stdin);

    freopen("maxflowd.out","w",stdout);

    int x,y;

    n=read();S=read(),T=read();

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

      for(int j=1;j<=n;j++)

        {

            x=read(),y=read();

            if(x) add(i,j,x,y);

        }

    mincost();

    printf("%d",ans);

    return 0;

}

巴特西

Cogs 13. 运输问题4(费用流)

最新文章

热门文章