[网络流24题] 运输问题 (费用流)

和分配问题这题的建图一模一样啊...这题只不过是多了个流量限制

首先题目保证货物总量和仓库容量相等，考虑最大流

源点$S$向每个仓库连流量为$a_{i}$，费用为$0$的边，每个商店向汇点连流量为$b_{i}$，费用为$0$的边，代表货物总量和商店容量

由于仓库可以向商店随便运货，只要仓库有足够多货且商店能装下就行，所以每个仓库$i$和每个商店$j$之间连一条流量为$inf$，费用为$c_{i,j}$的边

然后上费用流就行了

  1 #include <vector>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 205
  6 #define M1 50010
  7 #define ll long long
  8 #define dd double
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 
 12 int gint()
 13 {
 14     int ret=0,fh=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 17     return ret*fh;
 18 }
 19 
 20 int n,m,nm,S,T;
 21 int flow[N1][N1],cost[N1][N1],f[N1][N1],c[N1][N1];
 22 int que[M1],hd,tl,C[N1],F[N1],pre[N1];
 23 
 24 namespace S1{
 25 void bfs()
 26 {
 27     int x,i,v;
 28     memset(C,0x3f,sizeof(C)); memset(F,0,sizeof(F)); 
 29     hd=1,tl=0; que[++tl]=S; C[S]=0; F[S]=inf;
 30     while(hd<=tl)
 31     {
 32         x=que[hd++];
 33         for(v=1;v<=nm;v++)
 34         {
 35             if(!flow[x][v]) continue; 
 36             if(C[v]>C[x]+cost[x][v]) 
 37             {
 38                 C[v]=C[x]+cost[x][v];
 39                 F[v]=min(F[x],flow[x][v]);
 40                 que[++tl]=v; pre[v]=x;
 41             }
 42         }
 43     }
 44 } 
 45 void Dinic()
 46 {
 47     memcpy(cost,c,sizeof(c)); memcpy(flow,f,sizeof(f));
 48     int cash=0,tmp,x;
 49     while(1)
 50     {
 51         bfs(); if(!F[T]) break;
 52         for(x=T;x!=S;x=pre[x]) 
 53             flow[pre[x]][x]-=F[T],flow[x][pre[x]]+=F[T];
 54         cash+=C[T]*F[T];
 55     }
 56     printf("%d
",cash);
 57 }
 58 };
 59 
 60 namespace S2{
 61 void bfs()
 62 {
 63     int x,v;
 64     memset(C,-0x3f,sizeof(C)); memset(F,0,sizeof(F)); 
 65     hd=1,tl=0; que[++tl]=S; C[S]=0; F[S]=inf;
 66     while(hd<=tl)
 67     {
 68         x=que[hd++];
 69         for(v=1;v<=nm;v++)
 70         {
 71             if(!flow[x][v]) continue; 
 72             if(C[v]<C[x]+cost[x][v]) 
 73             {
 74                 C[v]=C[x]+cost[x][v];
 75                 F[v]=min(F[x],flow[x][v]);
 76                 que[++tl]=v; pre[v]=x;
 77             }
 78         }
 79     }
 80 } 
 81 void Dinic()
 82 {
 83     memcpy(cost,c,sizeof(c)); memcpy(flow,f,sizeof(f));
 84     int cash=0,tmp,x;
 85     while(1)
 86     {
 87         bfs(); if(!F[T]) break;
 88         for(x=T;x!=S;x=pre[x]) 
 89             flow[pre[x]][x]-=F[T],flow[x][pre[x]]+=F[T];
 90         cash+=C[T]*F[T];
 91     }
 92     printf("%d
",cash);
 93 }
 94 };
 95 
 96 int a[N1],b[N1];
 97 
 98 int main()
 99 {
100     scanf("%d%d",&m,&n); nm=n+m+2;
101     int i,j,v,ans; S=n+m+1,T=n+m+2;
102     for(i=1;i<=m;i++) scanf("%d",&a[i]), f[S][i]=a[i], c[S][i]=0;
103     for(i=m+1;i<=m+n;i++) scanf("%d",&b[i]), f[i][T]=b[i], c[i][T]=0;
104     for(i=1;i<=m;i++) for(j=m+1;j<=m+n;j++) 
105         scanf("%d",&c[i][j]),c[j][i]=-c[i][j], f[i][j]=inf, f[j][i]=0;
106     S1::Dinic(); S2::Dinic(); 
107     return 0;
108 }