当前位置:必发365电子游戏 > 编程 > 【必发365电子游戏】网络流24题供给嘲讽了,饭店向公司连
【必发365电子游戏】网络流24题供给嘲讽了,饭店向公司连
2019-12-19

2014年3月7日1,6360

【互联网流24题】运输难题(花销流)

必发365电子游戏,难题陈诉 Description

W 集团有m个货仓和n 个中间商铺。第i 个旅馆有ai 个单位的物品;第j 个零售集团
内需bj个单位的货物。货色供应和需要平衡,即  sum(si)=sum(bj卡塔尔(英语:State of Qatar)
。从第i 个货仓运送每单位货品到
第j 个零售公司的资费为cij 。试设计一个将酒店中持有商品运送到零售集团的运载方案,
使总运输花费起码。
编制程序职务:
对此给定的m 个旅舍和n 个经销商铺间运送商品的费用,总括最优铁路运输综合作业方案和最差铁路运输综合作业方案。

题面

Cogs

输入描述 Input Description

的第1行有2 个正整数m和n,分别代表货仓数和
零售杂货店数。接下来的豆蔻梢头行中有m个正整数ai ,1≤i≤m,表示第i个仓库有ai 个单位的货
物。再接下来的风姿罗曼蒂克行中有n个正整数bj ,1≤j≤n,表示第j个零售公司索要bj 个单位的货
物。接下来的m行,每行有n个整数,表示从第i 个饭店运送每单位货色到第j个零售集团
的费用cij 。

题解

大水题。。。
源点向仓库连,容积为货品量,花销为0
宾馆向厂家连,体积INF,开销难点给出去了
厂家向汇点连,体量为需要量,开支为0
大致裸的开支流

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 5000
#define MAXL 500000
#define INF 1000000000
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line
{
    int v,next,w,fy;
}e[MAXL];
bool vis[MAX];
int h[MAX],cnt=2;
int a[MAX],b[MAX],c[MAX][MAX];
inline void Add(int u,int v,int w,int fy)
{
    e[cnt]=(Line){v,h[u],w,fy};h[u]=cnt++;
    e[cnt]=(Line){u,h[v],0,-fy};h[v]=cnt++;
}
int pe[MAX],pr[MAX],dis[MAX];
int S,T,Cost,n,m,Flow,opt=1;
bool SPFA()
{
    memset(dis,63,sizeof(dis));
    queue<int> Q;
    Q.push(S);dis[S]=0;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=h[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(e[i].w&&dis[v]>dis[u]+e[i].fy)
            {
                dis[v]=dis[u]+e[i].fy;
                pe[v]=i;pr[v]=u;
                if(!vis[v])vis[v]=true,Q.push(v);
            }
        }
        vis[u]=false;
    }
    if(dis[T]>=INF)return false;
    int flow=INF;
    for(int i=T;i!=S;i=pr[i])flow=min(flow,e[pe[i]].w);
    for(int i=T;i!=S;i=pr[i])e[pe[i]].w-=flow,e[pe[i]^1].w+=flow;
    Cost+=opt*flow*dis[T];
    Flow+=flow;
    return true;
}
int main()
{
    freopen("tran.in","r",stdin);
    freopen("tran.out","w",stdout);
    m=read();n=read();
    for(int i=1;i<=m;++i)a[i]=read();
    for(int j=1;j<=n;++j)b[j]=read();
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            c[i][j]=read();
    S=0;T=n+m+1;

    memset(h,0,sizeof(h));cnt=2;
    for(int i=1;i<=m;++i)Add(S,i,a[i],0);
    for(int j=1;j<=n;++j)Add(j+m,T,b[j],0);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            Add(i,j+m,INF,c[i][j]);
    Cost=Flow=0;opt=1;
    while(SPFA());
    printf("%dn",Cost);

    memset(h,0,sizeof(h));cnt=2;
    for(int i=1;i<=m;++i)Add(S,i,a[i],0);
    for(int j=1;j<=n;++j)Add(j+m,T,b[j],0);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            Add(i,j+m,INF,-c[i][j]);
    Cost=Flow=0;opt=-1;
    while(SPFA());
    printf("%dn",Cost);

    return 0;
}

输出描述 Output Description

将计算出的起码运输支出和最多运输支出输出

样例输入 萨姆ple Input

2 3
220 280
170 120 210
77 39 105
150 186 122

样例输出 Sample Output

48500
69140

少年老成道水题,网络流24题须要作弄了,上下界的网络流未有

必发365电子游戏 1

跑得挺快的。

很好构图,正是S向侧边的点,连ai个单位,费用为0,左侧向T连bi个单位,费用为0

然后左边向右边流量Infiniti,花销c[i][【必发365电子游戏】网络流24题供给嘲讽了,饭店向公司连。j],即可,hh。

  1 #include<cstring>
  2 #include<cmath>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cstdio>
  6 #include<queue>
  7 
  8 #define N 2007
  9 #define M 1000007
 10 #define inf 1000000007
 11 using namespace std;
 12 inline int read()
 13 {
 14     int x=0,f=1;char ch=getchar();
 15     while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();}
 16     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 17     return x*f;
 18 }
 19 
 20 int m,n,S,T;
 21 int cnt=1,head[N],next[M],rea[M],val[M],cost[M];
 22 int c[N][N],a[N],b[N];
 23 int dis[N],flag[N];
 24 struct Node
 25 {
 26     int e,fa;
 27     void init(){e=fa=-1;}
 28 }pre[N];
 29 
 30 void add(int u,int v,int fee,int pay)
 31 {
 32     next[++cnt]=head[u];
 33     head[u]=cnt;
 34     rea[cnt]=v;
 35     val[cnt]=fee;
 36     cost[cnt]=pay;
 37 }
 38 void build(int k)
 39 {
 40     memset(head,-1,sizeof(head));cnt=1;
 41     for (int i=1;i<=m;i++)
 42     {
 43         int x=a[i];
 44         add(S,i,x,0),add(i,S,0,0);
 45     }
 46     for (int i=1;i<=n;i++)
 47     {
 48         int x=b[i];
 49         add(m+i,T,x,0),add(T,m+i,0,0);
 50     }
 51     for (int i=1;i<=m;i++)
 52         for (int j=1;j<=n;j++)
 53         {
 54             int x=c[i][j];
 55             add(i,m+j,inf,x*k),add(m+j,i,0,-x*k);
 56         }
 57 }
 58 bool Spfa()
 59 {
 60     for (int i=S;i<=T;i++)
 61         dis[i]=inf,flag[i]=0,pre[i].init();
 62     queue<int>q;q.push(S);
 63     dis[S]=0,flag[S]=1;
 64     while(!q.empty())
 65     {
 66         int u=q.front();q.pop();
 67         for (int i=head[u];i!=-1;i=next[i])
 68         {
 69             int v=rea[i],fee=cost[i];
 70             if ((dis[v]>dis[u]+fee)&&val[i]>0)
 71             {
 72                 dis[v]=dis[u]+fee;
 73                 pre[v].e=i,pre[v].fa=u;
 74                 if (!flag[v])
 75                 {
 76                     flag[v]=1;
 77                     q.push(v);
 78                 }
 79             }
 80         }    
 81         flag[u]=0;
 82     }
 83     if (dis[T]==inf) return 0;
 84     else return 1;
 85 }
 86 int mfmc()
 87 {
 88     int flow=0,res=0;
 89     while(Spfa())
 90     {
 91         int x=inf;
 92         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
 93         {
 94             int e=pre[i].e;
 95             x=min(x,val[e]);
 96         }
 97         flow+=x,res+=dis[T]*x;
 98         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
 99         {
100             int e=pre[i].e;
101             val[e]-=x,val[e^1]+=x;
102         }
103     }
104     return res;
105 }
106 int main()
107 {
108     m=read(),n=read();S=0,T=n+m+1;
109     for (int i=1;i<=m;i++) a[i]=read();
110     for (int i=1;i<=n;i++) b[i]=read();
111     for (int i=1;i<=m;i++)
112         for (int j=1;j<=n;j++)
113             c[i][j]=read();
114     build(1);
115     printf("%dn",mfmc());
116     build(-1);
117     printf("%dn",-mfmc());
118 }