P4015 运输问题
大意
在保证所有货物运出的前提下，分别寻找总开销最省和最贵的路径方案。
思路
首先来说，我们对于这些货物和商店来说，最终要保证最大流，就是 \(in = out\)，那么我们考虑一个事情，就是我们的货物如何运，运到哪里，运多少，我们是不关心的，那么中间我们就可以把每个货物和商店连上容量为正无穷的边，也就是对网络流说：“你爱怎么选怎么选，只要跑出来使得我花费最小即可”。
但是我们需要考虑货物的量和商店需要的量，这个东西我们其实可以在 \(S\) 和 \(T\) 的部分就将其设定住，这样就能保证最终所有货物都有所归（方案很多，一定能保证流最大，且为 \(\sum a_i\)），那么我们就建出图，跑两次费用流即可。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 5005;
const int MAXM = 40005;
struct node{int u, v, nxt, c, w;
}e[MAXM * 4];int S, T;
int tot, h[MAXN], d[MAXN], pre[MAXN];
bool vis[MAXN];
void init(){tot = 0;memset(h, -1, sizeof(h));
}void add(int u, int v, int c, int w){e[tot] = {u, v, h[u], c, w};h[u] = tot ++;e[tot] = {v, u, h[v], 0, -w};h[v] = tot ++;
}bool spfa(){memset(vis, 0, sizeof(vis));memset(d, 0x3f, sizeof(d));memset(pre, -1, sizeof(pre));queue<int> q;q.push(S);d[S] = 0;vis[S] = true;while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c){if(d[v] > d[u] + e[i].w){d[v] = d[u] + e[i].w;pre[v] = i;if(!vis[v]){q.push(v);vis[v] = true;}}}}}return (pre[T] != -1);
}int EK(){int res = 0;while(spfa()){int Min = 1e9;for(int i = T;i != S;i = e[pre[i]].u){Min = min(Min, e[pre[i]].c);}for(int i = T;i != S;i = e[pre[i]].u){e[pre[i]].c -= Min;e[pre[i] ^ 1].c += Min;res += e[pre[i]].w * Min;}}return res;
}int n, m;
int a[MAXN], b[MAXN], H[105][105];int main(){// freopen("dolls.in", "r", stdin);// freopen("dolls.out", "w", stdout);cin >> m >> n;S = 0, T = n + m + 1;for(int i = 1;i <= m;i ++) cin >> a[i];for(int j = 1;j <= n;j ++) cin >> b[j];for(int i = 1;i <= m;i ++){for(int j = 1;j <= n;j ++){cin >> H[i][j];}}init();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, 1e9, H[i][j]);}}cout << EK() << endl;init();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, 1e9, -H[i][j]);}}cout << -EK() << endl;return 0;
}