洛谷 P4015 运输问题（费用流）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int N=5005;
 8 const int INF=0x3f3f3f;
 9 int head[N],vis[N],pre[N],dis[N],a[N],b[N],c[N][N];
10 int tot,m,n,cost;
11 struct node{
12     int from,to,next,flow,cost;
13 }edge[N<<1];
14 void add(int u,int v,int flow,int cost){
15     edge[tot].from=u;
16     edge[tot].to=v;
17     edge[tot].next=head[u];
18     edge[tot].flow=flow;
19     edge[tot].cost=cost;
20     head[u]=tot++;
21     
22     edge[tot].from=v;
23     edge[tot].to=u;
24     edge[tot].next=head[v];
25     edge[tot].flow=0;
26     edge[tot].cost=-cost;
27     head[v]=tot++;
28 }
29 void init(){
30     memset(head,-1,sizeof(head));
31     tot=0;
32 }
33 int spfa(int s,int t){
34     memset(dis,INF,sizeof(dis));
35     memset(vis,0,sizeof(vis));
36     memset(pre,-1,sizeof(pre));
37     queue<int> q;
38     q.push(s); vis[s]=1; dis[s]=0;
39     while(!q.empty()){
40         int u=q.front(); q.pop(); vis[u]=0;
41         for(int i=head[u];i!=-1;i=edge[i].next){
42             int v=edge[i].to;
43             if(edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
44                 dis[v]=dis[u]+edge[i].cost;
45                 pre[v]=i;
46                 if(vis[v]==0){
47                     q.push(v);
48                     vis[v]=1;
49                 }
50             }
51         }
52     }
53     if(pre[t]==-1) return 0;
54     return 1; 
55 }
56 void MCMF(int s,int t){
57     cost=0;
58     while(spfa(s,t)){
59         int minn=INF;
60         for(int i=pre[t];i!=-1;i=pre[edge[i].from])
61             minn=min(minn,edge[i].flow);
62         for(int i=pre[t];i!=-1;i=pre[edge[i].from]){
63             edge[i].flow-=minn;
64             edge[i^1].flow+=minn;
65         }
66         cost+=minn*dis[t];
67     }
68 }
69 int main(){
70     init();
71     scanf("%d%d",&m,&n);
72     int s=0,t=m+n+1;
73     for(int i=1;i<=m;i++) {scanf("%d",&a[i]); add(s,i,a[i],0);}
74     for(int i=1;i<=n;i++) {scanf("%d",&b[i]); add(i+m,t,b[i],0);}
75     for(int i=1;i<=m;i++)
76     for(int j=1;j<=n;j++){
77         scanf("%d",&c[i][j]);
78         add(i,j+m,INF,c[i][j]);
79     }
80     MCMF(s,t);
81     printf("%d
",cost);
82     init();
83     for(int i=1;i<=m;i++) add(s,i,a[i],0);
84     for(int i=1;i<=n;i++) add(i+m,t,b[i],0);
85     for(int i=1;i<=m;i++)
86     for(int j=1;j<=n;j++)
87         add(i,j+m,INF,-c[i][j]);
88     MCMF(s,t);
89     printf("%d",-cost);
90     return 0;
91 }