记录编号	152276	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2010] 网络扩容	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2015-03-13 21:55:36	内存使用	0.72 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct adj{
   int from,to,cost,cap,flow;
   adj(int from=0,int to=0,int cost=0,int cap=0,int flow=0):from(from),to(to),cost(cost),cap(cap),flow(flow){}
};
///==============var declaration=================
const int MAXN=1050;
int n,m,k,tot=0;
int cur[MAXN],pa[MAXN],d[MAXN],gap[MAXN];
bool inq[MAXN];
vector <int> G[MAXN];
adj Edge[20050];
///==============function declaration============
void add_edge(int from,int to,int cost,int cap,int flow);
int argument();bool spfa();
void MaxFlow();void ReBuild();void MinCost();void bfs();
///==============main code=======================
int main()
{
   freopen("networkzj2010.in","r",stdin);
   freopen("networkzj2010.out","w",stdout);
   scanf("%d%d%d",&n,&m,&k);
   for(int i=1;i<=m;i++){
      int s,e,c,w;
      scanf("%d%d%d%d",&s,&e,&c,&w);
      add_edge(s,e,w,c,0);
   }
   MaxFlow();
   ReBuild();
   MinCost();
   return 0;
}
///================fuction code====================
void add_edge(int from,int to,int cost,int cap,int flow){
   Edge[tot]=adj(from,to,cost,cap,flow);
   G[from].push_back(tot++);
   Edge[tot]=adj(to,from,-cost,0,0);
   G[to].push_back(tot++);
}
void MaxFlow(){
   memset(d,-1,sizeof(d));memset(cur,0,sizeof(cur));
   bfs();
   int flow=0,x=1;
   while (d[1]<=n-1){
      if (x==n){
         flow+=argument();
         x=1;
      }
      int siz=G[x].size();bool suc=false;
      for(int i=cur[x];i<siz;i++){
         adj &e=Edge[G[x][i]];
         if (e.cap>e.flow&&d[e.to]==d[x]-1){
            pa[e.to]=G[x][i];cur[x]=i;
            x=e.to;suc=true;break;
         }
      }
      if (!suc){
         int mind=n-1;
         for(int i=0;i<siz;i++){
            adj &e=Edge[G[x][i]];
            if (e.cap>e.flow)
               mind=min(mind,d[e.to]);
         }
         if (--gap[d[x]]==0)  break;
         gap[d[x]=mind+1]++;cur[x]=0;
         if (x!=1)  x=Edge[pa[x]].from;
      }
   }
   printf("%d\n",flow);
}
void bfs(){
   queue <int> Q;Q.push(n);d[n]=0;
   while (!Q.empty()){
      int x=Q.front();Q.pop();
      gap[d[x]]++;
      int siz=G[x].size();
      for(int i=0;i<siz;i++){
         adj &e=Edge[G[x][i]];
         if (d[e.to]==-1){
            d[e.to]=d[x]+1;
            Q.push(e.to);
         }
      }
   }
}
int argument(){
   int x=n,flow=INF;
   while (x!=1){
      adj &e=Edge[pa[x]];
      flow=min(flow,e.cap-e.flow);
      x=e.from;
   }
   x=n;
   while (x!=1){
      Edge[pa[x]].flow+=flow;
      Edge[pa[x]^1].flow-=flow;
      x=Edge[pa[x]].from;
   }
   return flow;
}
void ReBuild(){
   int from,to;int tmp=tot;
   for(int i=0;i<tmp;i+=2){
      adj &e=Edge[i];
      from=e.from,to=e.to;
      add_edge(from,to,e.cost,INF,0);
      e.cost=0;Edge[i^1].cost=0;
   }
}
void MinCost(){
   int flow=0,ans=0;
   while (flow<k){
      spfa();
      int x=n,add_flow=INF;
      while (x!=1){
         adj &e=Edge[pa[x]];
         add_flow=min(add_flow,e.cap-e.flow);
         x=e.from;
      }
      x=n;
      while (x!=1){
         Edge[pa[x]].flow+=add_flow;
         Edge[pa[x]^1].flow-=add_flow;
         x=Edge[pa[x]].from;
      }
      if (flow+add_flow<=k)
         ans+=add_flow*d[n];
      else
         ans+=(k-flow)*d[n];
      flow+=add_flow;
   }
   printf("%d\n",ans);
}
bool spfa(){
   for(int i=1;i<=n;i++) d[i]=INF;d[1]=0;
   memset(inq,false,sizeof(inq));
   queue <int> Q;Q.push(1);
   while (!Q.empty()){
      int x=Q.front();Q.pop();
      int siz=G[x].size();inq[x]=false;
      for(int i=0;i<siz;i++){
         adj &e=Edge[G[x][i]];
         if (e.cap<=e.flow) continue;
         if (d[e.to]>d[x]+e.cost){
            d[e.to]=d[x]+e.cost;
            pa[e.to]=G[x][i];
            if (!inq[e.to])
               Q.push(e.to);
            inq[e.to]=true;
         }
      }
   }
   return true;
}