HDU 3667 Transportation (最小费用最大流)
题意：
有N个城市M条道路，现在你要把K个物品从城市1转移到城市N，每条道路转移x个物品需要ai *x^2费用，并且每条道路都有转移物品个数的上限，问你转移这K个物品最小费用为多少，若不能转移，输出-1.
解题思路：
对于每条道路建边每个容量为1的费用分别为ai , 3*ai, 5*ai ... (x^2 - (x-1)^2) *ai ，因为如果流量为1，肯定是走ai这条路，如果流量为2，肯定是走ai和3ai，所以就转化成普通的最小费用最大流问题。
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define pii pair<int,int>#define mk_p make_pairconst int maxn = 100 + 5;const int maxm = 500000 + 5;const int INF = 2000000000;struct Edge { int u, to, cap, cost, next; Edge(){} Edge(int _u, int _to, int _cap, int _cost, int _next) { u = _u; to = _to; cap = _cap; cost = _cost; next = _next; }}edge[maxm<<1];int head[maxn], E, dist[maxn], pp[maxn];bool vis[maxn];void init(int n) { for(int i = 0;i <= n; i++) head[i] = -1; E = 0;}void newedge(int u, int to, int cap, int cost) { edge[E] = Edge(u, to, cap, cost, head[u]); head[u] = E++; edge[E] = Edge(to, u, 0, -cost, head[to]); head[to] = E++;}int qu[333333];bool SPFA(int s, int t, int n) { for(int i = 0;i <= n; i++) { vis[i] = 0; pp[i] = -1; dist[i] = INF; } vis[s] = true; int st = 0, ed = 0; qu[ed++] = s; dist[s] = 0; while(st < ed) { int u = qu[st++]; vis[u] = false; for(int i = head[u];i != -1;i = edge[i].next) { int to = edge[i].to; int tmp = dist[u] + edge[i].cost; if(edge[i].cap && dist[to] > tmp) { dist[to] = tmp; pp[to] = i; if(!vis[to]) { qu[ed++] =to; vis[to] = true; } } } } if(dist[t] == INF) return false; return true;}// 最小费用最大流pii MCMF(int s, int t, int n) { int flow = 0; int mincost = 0; while(SPFA(s, t, n)) { int minflow = INF; for(int i = pp[t];i != -1;i = pp[edge[i].u]) if(minflow > edge[i].cap) minflow = edge[i].cap; flow += minflow; for(int i = pp[t];i != -1;i = pp[edge[i].u]) { edge[i].cap -= minflow; edge[i^1].cap += minflow; } mincost += dist[t]*minflow; } return mk_p(flow, mincost);}int n, m, k, u, to, a, c;void solve() { init(n+1); // 建边 for(int i = 0;i < m; i++) { scanf("%d%d%d%d", &u, &to, &a, &c); int top = min(k, c); for(int j = 1;j <= top; j++) newedge(u, to, 1, a*( j*j - (j-1)*(j-1))); } newedge(n, n+1, k, 0); pii ans = MCMF(1, n+1, n+1); if(ans.first < k) puts("-1"); else printf("%d\n", ans.second);}int main() { while(scanf("%d%d%d", &n, &m, &k) != -1) { solve(); } return 0;}