运输问题

题目链接：https://www.luogu.org/problemnew/show/P4015

　题解：

　　明显是个最小/大费用最大流。思路很简单，主要是求最大费用的时候有个小技巧，就是不能直接拿spfa求，要先把所有边的费用取反然后求最小费用，输出时再取反。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<bitset>
  8 #define LL long long
  9 #define RI register int
 10 using namespace std;
 11 const int INF = 0x7ffffff ;
 12 const int N = 100 + 10 ;
 13 const int M = 5e4 + 10 ;
 14 const int NN = 1e4 + 10 ;
 15 
 16 inline int read() {
 17     int k = 0 , f = 1 ; char c = getchar() ;
 18     for( ; !isdigit(c) ; c = getchar())
 19       if(c == '-') f = -1 ;
 20     for( ; isdigit(c) ; c = getchar())
 21       k = k*10 + c-'0' ;
 22     return k*f ;
 23 }
 24 struct Edge {
 25     int to, next, flow, cost ;
 26 }e[M] ;
 27 int n, m, s, t, ansf, ansc, cnt = 1 ; int aa[N], bb[N], head[NN], dis[NN], hh[N][N] ; bool vis[NN] ;
 28 inline void add_edge(int x,int y,int ff,int cc) {
 29 //    static int cnt = 1 ;
 30     e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt, e[cnt].flow = ff, e[cnt].cost = cc ;
 31     e[++cnt].to = x, e[cnt].next = head[y], head[y] = cnt, e[cnt].flow = 0, e[cnt].cost = -cc ;
 32 }
 33 
 34 inline bool spfa() {
 35     for(int i=1;i<=NN;i++) dis[i] = INF ; bitset<NN>inq ;
 36     deque<int>q ; q.push_back(s) ; dis[s] = 0 ; inq[s] = 1 ;
 37     while(!q.empty()) {
 38         int x = q.front() ; q.pop_front() ;
 39         for(int i=head[x];i;i=e[i].next) {
 40             int y = e[i].to ; if(!e[i].flow) continue ;
 41             if(dis[y] > dis[x]+e[i].cost) {
 42                 dis[y] = dis[x]+e[i].cost ;
 43                 if(!inq[y]) {
 44                     inq[y] = 1 ;
 45                     if(!q.empty() && dis[y] < dis[q.front()]) q.push_front(y) ;
 46                     else q.push_back(y) ;
 47                 }
 48             }
 49         }
 50         inq[x] = 0 ;
 51     }
 52     return dis[t] < INF ;
 53 }
 54 /*
 55 inline bool spfa2() {
 56     memset(dis,-1,sizeof(dis)) ; bitset<NN>inq ;
 57     queue<int>q ; q.push(s) ; inq[s] = 1 ; dis[s] = 0 ;
 58     while(!q.empty()) {
 59         int x = q.front() ; q.pop() ;
 60         for(int i=head[x];i;i=e[i].next) {
 61             int y = e[i].to ; if(!e[i].flow) continue ;
 62             if(dis[y] < dis[x]+e[i].cost) {
 63                 dis[y] = dis[x]+e[i].cost ;
 64                 if(!inq[y]) {
 65                     inq[y] = 1 ;
 66                     q.push(y) ;
 67                 }
 68             }
 69         }
 70         inq[x] = 0 ;
 71     }
 72     return dis[t] > -1 ;
 73 }
 74 */
 75 int FFdfs(int x,int minflow) {
 76     if(x == t || !minflow) {
 77         vis[x] = 1 ; return minflow ;
 78     }
 79     int fflow = 0 ; vis[x] = 1 ;
 80     for(int i=head[x];i;i=e[i].next) {
 81         int y = e[i].to ; if(!e[i].flow || vis[y] || dis[y] != dis[x]+e[i].cost) continue ;
 82         int temp = FFdfs(y,min(minflow,e[i].flow)) ;
 83         fflow += temp, minflow -= temp ;
 84         e[i].flow -= temp, e[i^1].flow += temp ;
 85         ansc += temp*e[i].cost ;
 86         if(!minflow) break ;
 87     }
 88     return fflow ;
 89 }
 90 
 91 int main() {
 92 //    freopen("tran.in","r",stdin) ;
 93 //    freopen("tran.out","w",stdout) ;
 94     m = read(), n = read() ; s = m+n+1, t = s+1 ;
 95     for(int i=1;i<=m;i++) aa[i] = read() ;
 96     for(int i=1;i<=n;i++) bb[i] = read() ;
 97     for(int i=1;i<=m;i++) 
 98       for(int j=1;j<=n;j++) hh[i][j] = read() ;
 99     for(int i=1;i<=m;i++) {
100         add_edge(s,i,aa[i],0) ;
101         for(int j=1;j<=n;j++) add_edge(i,j+m,aa[i],hh[i][j]) ; 
102     }
103     for(int i=1;i<=n;i++) add_edge(i+m,t,bb[i],0) ;
104     while(spfa()) {
105         vis[t] = 1 ;
106         while(vis[t]) {
107             memset(vis,0,sizeof(vis)) ;
108             ansf += FFdfs(s,INF) ;
109         }
110     }
111     printf("%d
",ansc) ;
112     ansc = 0, ansf = 0 ;
113     for(int i=2;i<=cnt;i+=2) e[i].cost *= -1, e[i].flow += e[i^1].flow, e[i^1].flow = 0, e[i^1].cost *= -1 ;
114     while(spfa()) {
115         vis[t] = 1 ;
116         while(vis[t]) {
117             memset(vis,0,sizeof(vis)) ;
118             ansf += FFdfs(s,INF) ;
119         }
120     }    
121     printf("%d",-ansc) ;
122     return 0 ;
123 }