beloved_ACM

  这题不能用邻接矩阵，因为有重边，但是费用或流量又不一样。做法是拆边，假设一条边的容量为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;
}