【題意】：有n個城市，m條有方向的路。你想從城市1運(yùn)輸k個單位的貨物到城市n，但每條路上都有很多強(qiáng)盜，因此通過每條路你都必須要小心的保護(hù)好你的貨物。對于每條路i，給出一個系數(shù)ai，如果你想在這條路上運(yùn)輸x個單位的貨物，就要花費(fèi)ai*x*x的費(fèi)用以便去保護(hù)你的貨物；再給出一個ci，表示在這條路上最多運(yùn)輸ci個單位的貨物。如果能運(yùn)輸完所有貨物的話，輸出最小的費(fèi)用；否則，輸出-1。
【題解】：這題好明顯是一個最小費(fèi)用流的模型。但問題在于，通過每條路的費(fèi)用不是跟流成正比，而是跟流的平方成正比。
觀察數(shù)據(jù)，發(fā)現(xiàn)每條路的容量ci <= 5，是不是覺得好奇怪，為什么邊的容量ci <= 5。其實，題目這是在暗示我們要拆邊。
舉一個例子，有邊<u,v>，c為5，a為1。
我們在<u,v>上分別運(yùn)輸x個單位貨物：
x 1 2 3 4 5
cost 1 4 9 16 25
cost[x] - cost[x-1] 3 5 7 9 觀察這一行，顯然這是一個等差數(shù)列。 n^2 = 1 + 3 + 5 + … +（2n - 1). [關(guān)鍵：拆邊的依據(jù)]
觀察到這個規(guī)律：我們就可以對所有邊<u,v> ,ai,ci這樣處理，把當(dāng)前邊拆分成 ci 條<u,v>邊，每條邊的費(fèi)用是 （2*i - 1）* ai [ 1 <= i <= ci ]，容量都是1。為了下面方便，我們叫這樣的ci條邊為一組邊。
拆完之后，圖上每條邊的容量都變成1，而且邊上的費(fèi)用跟流成正比。
對于每組邊的選擇，我們肯定是從編號小的先選起，因為編號小的費(fèi)用小。假如對于某組邊，我們選擇了其中x條，那就意味著我們在原<u,v>邊上運(yùn)輸了x個單位的貨物，那么費(fèi)用應(yīng)該是ai*x*x。而前x條邊的費(fèi)用總和 = [ 1 + 3 + … + （2 * x - 1）] * ai = x*x*ai。這就證明了我們拆邊的正確性。
又因為題目問最終能否運(yùn)輸完k個單位的貨物，對于這個問題我們有兩種處理辦法：
1.加入一個超級源點(diǎn)s，連邊s->1，容量為k，費(fèi)用為0.表示最多運(yùn)k個單位貨物。
2.限制費(fèi)用流運(yùn)行的條件，平時費(fèi)用流限制條件是能否找到增廣路，我們只需再加入一個條件，ans < k（ans表示當(dāng)前的費(fèi)用流的流量）。
最后判斷一下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 }