【题意】：有n个城市，m条有方向的路。你想从城市1运输k个单位的货物到城市n，但每条路上都有很多强盗，因此通过每条路你都必须要小心的保护好你的货物。对于每条路i，给出一个系数ai，如果你想在这条路上运输x个单位的货物，就要花费ai*x*x的费用以便去保护你的货物；再给出一个ci，表示在这条路上最多运输ci个单位的货物。如果能运输完所有货物的话，输出最小的费用；否则，输出-1。
【题解】：这题好明显是一个最小费用流的模型。但问题在于，通过每条路的费用不是跟流成正比，而是跟流的平方成正比。
观察数据，发现每条路的容量ci <= 5，是不是觉得好奇怪，为什么边的容量ci <= 5。其实，题目这是在暗示我们要拆边。
举一个例子，有边<u,v>，c为5，a为1。
我们在<u,v>上分别运输x个单位货物：
x 1 2 3 4 5
cost 1 4 9 16 25
cost[x] - cost[x-1] 3 5 7 9 观察这一行，显然这是一个等差数列。 n^2 = 1 + 3 + 5 + … +（2n - 1). [关键：拆边的依据]
观察到这个规律：我们就可以对所有边<u,v> ,ai,ci这样处理，把当前边拆分成 ci 条<u,v>边，每条边的费用是 （2*i - 1）* ai [ 1 <= i <= ci ]，容量都是1。为了下面方便，我们叫这样的ci条边为一组边。
拆完之后，图上每条边的容量都变成1，而且边上的费用跟流成正比。
对于每组边的选择，我们肯定是从编号小的先选起，因为编号小的费用小。假如对于某组边，我们选择了其中x条，那就意味着我们在原<u,v>边上运输了x个单位的货物，那么费用应该是ai*x*x。而前x条边的费用总和 = [ 1 + 3 + … + （2 * x - 1）] * ai = x*x*ai。这就证明了我们拆边的正确性。
又因为题目问最终能否运输完k个单位的货物，对于这个问题我们有两种处理办法：
1.加入一个超级源点s，连边s->1，容量为k，费用为0.表示最多运k个单位货物。
2.限制费用流运行的条件，平时费用流限制条件是能否找到增广路，我们只需再加入一个条件，ans < k（ans表示当前的费用流的流量）。
最后判断一下ans是否等于k就可以了。
【代码】：
1 #include "iostream"
2 #include "cstring"
3 #include "cstdio"
4 #include "queue"
5 using namespace std;
6 #define maxn 105
7 #define maxm 100005
8 const int inf = 1 << 30;
9 int n, m, k, s, t;
10 int eh[maxn], low[maxn], tot, dist[maxn], pre[maxn], ans, anscost;
11 bool visit[maxn];
12
13 struct Edge {
14 int u, v, cost, cap, flow, next;
15 }et[maxm];
16
17 void init() {
18 tot = 0;
19 memset(eh, -1, sizeof(eh));
20 }
21
22 void add(int u, int v, int cost, int cap, int flow) {
23 Edge e = {u, v, cost, cap, flow, eh[u]};
24 et[tot] = e;
25 eh[u] = tot++;
26 }
27
28 void addedge(int u, int v, int cost, int cap) {
29 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
30 }
31
32 bool spfa() {
33 fill(&dist[0], &dist[maxn], inf);
34 memset(visit, false, sizeof(visit));
35 memset(pre, -1, sizeof(pre));
36 low[s] = inf, visit[s] = true, dist[s] = 0;
37 queue<int> que;
38 que.push(s);
39 while(!que.empty()) {
40 int u = que.front();
41 que.pop();
42 visit[u] = false;
43 for(int i = eh[u]; i != -1; i = et[i].next) {
44 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
45 if(cap - flow && dist[v] > dist[u] + cost) {
46 dist[v] = dist[u] + cost;
47 pre[v] = i;
48 low[v] = min(low[u], cap - flow);
49 if(!visit[v]) {
50 que.push(v);
51 visit[v] = true;
52 }
53 }
54 }
55 }
56 return dist[t] != inf;
57 }
58
59 void costflow() {
60 ans = anscost = 0;
61 while(ans < k && spfa()) {
62 int x = pre[t];
63 ans += low[t];
64 anscost += low[t] * dist[t];
65 while(x != -1) {
66 et[x].flow += low[t];
67 et[x^1].flow -= low[t];
68 x = pre[et[x].u];
69 }
70 }
71 }
72
73 int main() {
74 int u, v, cost, cap;
75 while(~scanf("%d%d%d", &n, &m, &k)) {
76 init();
77 s = 1, t = n;
78 for(int i = 0; i < m; i++) {
79 scanf("%d%d%d%d", &u, &v, &cost, &cap);
80 for(int j = 1; j <= cap; j++)
81 addedge(u, v, (2 * j - 1) * cost, 1);
82 }
83 costflow();
84 if(ans == k) printf("%d\n", anscost);
85 else printf("%d\n", -1);
86 }
87 return 0;
88 }