这题不能用邻接矩阵，因为有重边，但是费用或流量又不一样。做法是拆边，假设一条边的容量为ci，把每条边拆成ci条容量为1的边，取费用为1*a ,3*a,5*a 依次类推。
#include <iostream>
using namespace std;
#include <iostream>
#include <queue>
using namespace std;
const int INF = 0x7fffffff;
const int MAXN = 10001;
struct node {
int v;int next;
int flow;int cap;
int cost;
}space[4*MAXN];
int sps;
int k,u,v,ci,aa;
int edge[MAXN];
int c,f;
int first[MAXN];
int n,m;
int p[MAXN];
void addedge(int head[],int u,int v,int cap,int cost) {
space[sps].v = v;
space[sps].cap = cap;
space[sps].cost = cost;
space[sps].next = head[u];
space[sps].flow = 0;
head[u] = sps++;
space[sps].v = u;
space[sps].cap = 0;
space[sps].cost = -cost;
space[sps].next = head[v];
space[sps].flow = 0;
head[v] = sps++;
}
void solve() {
queue<int> q;
int d[MAXN];
c = f = 0;
int s = 1,t = n;
for(;f < k;) {
bool inq[MAXN];
for(int i = 0; i <= n+1; i++) d[i] = (i == s? 0 : INF);
memset(inq,0,sizeof(inq));
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int addr = first[u]; addr != -1; addr = space[addr].next) {
int v = space[addr].v;
if(space[addr].cap > space[addr].flow && d[v] > d[u] + space[addr].cost ) {
p[v]= u;
edge[v] = addr; //记录增广路u to v的编号。
d[v] = d[u] + space[addr].cost;
if(!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
if(d[t] == INF) break;
int a =INF;
for(int u = t; u!= s; u = p[u]) a = min(a,space[edge[u]].cap - space[edge[u]].flow);
for(int u = t; u != s; u = p[u]) {
space[edge[u]].flow += a;
space[edge[u]^1].flow -= a; //异或奇数边减-1偶数边加1，妙
}
c+= d[t] *a;
f += a;
}
}
int main() {
while(scanf("%d%d%d",&n,&m,&k)!=EOF) {
sps = 0;
memset(first,-1,sizeof(first));
for(int i = 0; i < m; i++) {
int num = 1;
scanf("%d%d%d%d",&u,&v,&aa,&ci);
for(int j = 0; j < ci; j++) {
addedge(first,u,v,1,aa*num);
num += 2;
}
}
// addedge(first,0,1,INF,0);
// addedge(first,n,n+1,INF,0);
solve();
if(f == k)
printf("%d\n",c);
else
printf("-1\n");
}
return 0;
}