运输问题（费用流）

运输问题

https://www.luogu.org/problemnew/show/P4015

题目描述

货物供需平衡

从第

试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

输入输出格式

输入格式：

第

接下来的一行中有 m

再接下来的一行中有

接下来的

输出格式：

两行分别输出最小运输费用和最大运输费用。

输入输出样例

输入样例#1：

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

输出样例#1：

48500
69140

说明

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 const int INF=0x3f3f3f3f;
  8 const int N=50005;
  9 const int M=500005;
 10 int top;
 11 int dist[N],pre[N];
 12 bool vis[N];
 13 int c[N];
 14 int maxflow;
 15 
 16 struct Vertex{
 17     int first;
 18 }V[N];
 19 struct Edge{
 20     int v,next;
 21     int cap,flow,cost;
 22 }E[M];
 23 
 24 void init(){
 25     memset(V,-1,sizeof(V));
 26     top=0;
 27     maxflow=0;
 28 }
 29 
 30 void add_edge(int u,int v,int c,int cost){
 31     E[top].v=v;
 32     E[top].cap=c;
 33     E[top].flow=0;
 34     E[top].cost=cost;
 35     E[top].next=V[u].first;
 36     V[u].first=top++;
 37 }
 38 
 39 void add(int u,int v,int c,int cost){
 40     add_edge(u,v,c,cost);
 41     add_edge(v,u,0,-cost);
 42 }
 43 
 44 bool SPFA(int s,int t,int n){
 45     int i,u,v;
 46     queue<int>qu;
 47     memset(vis,false,sizeof(vis));
 48     memset(c,0,sizeof(c));
 49     memset(pre,-1,sizeof(pre));
 50     for(i=1;i<=n;i++){
 51         dist[i]=INF;
 52     }
 53     vis[s]=true;
 54     c[s]++;
 55     dist[s]=0;
 56     qu.push(s);
 57     while(!qu.empty()){
 58         u=qu.front();
 59         qu.pop();
 60         vis[u]=false;
 61         for(i=V[u].first;~i;i=E[i].next){
 62             v=E[i].v;
 63             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 64                 dist[v]=dist[u]+E[i].cost;
 65                 pre[v]=i;
 66                 if(!vis[v]){
 67                     c[v]++;
 68                     qu.push(v);
 69                     vis[v]=true;
 70                     if(c[v]>n){
 71                         return false;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[t]==INF){
 78         return false;
 79     }
 80     return true;
 81 }
 82 
 83 int MCMF(int s,int t,int n){
 84     int d;
 85     int i,mincost;
 86     mincost=0;
 87     while(SPFA(s,t,n)){
 88         d=INF;
 89         for(i=pre[t];~i;i=pre[E[i^1].v]){
 90             d=min(d,E[i].cap-E[i].flow);
 91         }
 92         maxflow+=d;
 93         for(i=pre[t];~i;i=pre[E[i^1].v]){
 94             E[i].flow+=d;
 95             E[i^1].flow-=d;
 96         }
 97         mincost+=dist[t]*d;
 98     }
 99     return mincost;
100 }
101 
102 int aa[150];
103 int bb[150];
104 int ab[150][150];
105 
106 int main(){
107     int n,m;
108     int v,u,w,c;
109     int s,t;
110     cin>>m>>n;
111     init();
112     s=0,t=n*m+1;
113     for(int i=1;i<=m;i++){
114         cin>>aa[i];
115         add(s,i,aa[i],0);
116     }
117     for(int i=1;i<=n;i++){
118         cin>>bb[i];
119         add(m+i,t,bb[i],0);
120     }
121     for(int i=1;i<=m;i++){
122         for(int j=1;j<=n;j++){
123             cin>>ab[i][j];
124             add(i,m+j,INF,ab[i][j]);
125         }
126     }
127     int ans=MCMF(s,t,n*m+2);
128     cout<<ans<<endl;
129     init();
130     for(int i=1;i<=m;i++){
131         add(s,i,aa[i],0);
132     }
133     for(int i=1;i<=n;i++){
134         add(m+i,t,bb[i],0);
135     }
136     for(int i=1;i<=m;i++){
137         for(int j=1;j<=n;j++){
138             add(i,m+j,INF,-ab[i][j]);
139         }
140     }
141     ans=MCMF(s,t,n*m+2);
142     cout<<-ans<<endl;
143 }

View Code