【题意】:有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, -1sizeof(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, 00);
30 }
31 
32 bool spfa() {
33     fill(&dist[0], &dist[maxn], inf);
34     memset(visit, falsesizeof(visit));
35     memset(pre, -1sizeof(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 }