5 8 21 2 5 82 5 9 95 1 6 25 1 1 81 2 8 72 5 4 91 2 1 11 4 2 1

13 19

  1 /*  2     有重边对 max_flow()中找前驱有影响   3     所以在node中记录前驱就好了   4 */  5 #include<queue>  6 #include<cstdio>  7 #include<cstring>  8 #include<iostream>  9 #define MAXN 200010 10  11 using namespace std; 12  13 const int INF=0x7fffffff; 14  15 int n,m,k,MAX_FLOW,MIN_FEE,src; 16  17 int x,y,val,cost[MAXN],a[MAXN]; 18  19 struct node { 20     int from; 21     int to; 22     int next; 23     int val; 24     int cost; 25     int save; 26 }; 27 node e[MAXN]; 28  29 bool vis[MAXN]; 30  31 int head[MAXN],tot=1; 32  33 int fee[MAXN],pre[MAXN]; 34  35 queue<int> q; 36  37 inline void read(int&x) { 38     int f=1;x=0;char c=getchar(); 39     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();} 40     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();} 41     x=x*f; 42 } 43  44 inline void add(int x,int y,int val,int cost) { 45     e[++tot].to=y; 46     e[tot].from=x; 47     e[tot].val=val; 48     e[tot].cost=cost; 49     e[tot].next=head[x]; 50     head[x]=tot; 51 } 52  53 inline void add1(int x,int y,int val,int save) { 54     e[++tot].to=y; 55     e[tot].from=x; 56     e[tot].val=val; 57     e[tot].save=save; 58     e[tot].next=head[x]; 59     head[x]=tot; 60 } 61  62 inline void add_edge(int x,int y,int val,int cost) { 63     add(x,y,val,cost); 64     add(y,x,0,-cost); 65 } 66  67 inline void add_edge1(int x,int y,int val,int cost) { 68     add1(x,y,val,cost); 69     add1(y,x,0,-cost); 70 } 71  72 inline bool spfa_flow() { 73     for(int i=0;i<=n;i++) vis[i]=false,pre[i]=-1; 74     while(!q.empty()) q.pop(); 75     q.push(src); 76     fee[src]=0; 77     pre[src]=0; 78     vis[src]=true; 79     while(!q.empty()) { 80         int u=q.front(); 81         q.pop(); 82         for(int i=head[u];i;i=e[i].next) { 83             int to=e[i].to; 84             if(!vis[to]&&e[i].val) { 85                 pre[to]=i; 86                 vis[to]=true; 87                 if(to==n) return true; 88                 q.push(to); 89             } 90         } 91     } 92     return false; 93 } 94  95 inline int max_flow() { 96     int flow=INF; 97     for(int i=pre[n];i;i=pre[e[i^1].to])  98       flow=min(flow,e[i].val); 99     for(int i=pre[n];i;i=pre[e[i^1].to])100       e[i].val-=flow,e[i^1].val+=flow;101     return flow;102 }103 104 inline void change() {105     int pot=tot;106     for(int i=4;i<=pot;i++) 107       if(i%2==0) add_edge(e[i].from,e[i].to,INF,e[i].save);108     e[2].val=k;109     e[3].val=0;110     return;111 }112 113 inline bool spfa_fee() {114     for(int i=0;i<=n;i++) vis[i]=false,pre[i]=-1,fee[i]=INF;115     while(!q.empty()) q.pop();116     q.push(0);117     fee[0]=0;118     vis[0]=true;119     pre[0]=0;120     a[0]=999999;121     while(!q.empty()) {122         int u=q.front();123         q.pop();124         vis[u]=false;125         for(int i=head[u];i!=-1;i=e[i].next) {126             int to=e[i].to;127             if(fee[to]>fee[u]+e[i].cost&&e[i].val>0) {128                 a[to]=min(a[u],e[i].val);129                 fee[to]=fee[u]+e[i].cost;130                 pre[to]=i;131                 if(!vis[to]) {132                     vis[to]=true;133                     q.push(to);134                 }135             }136         }137     }138     return fee[n]!=INF;139 }140 141 inline int MIN_fee() {142     int Flow=INF;143     for(int i=pre[n];i;i=pre[e[i].from]) 144       Flow=min(Flow,e[i].val);145     for(int i=pre[n];i;i=pre[e[i].from])146       e[i].val-=Flow,e[i^1].to+=Flow;147     return Flow;148 }149 150 int main() {151     read(n);read(m);read(k);152     memset(head,-1,sizeof head);153     add_edge1(src,1,1<<30,0);154     for(int i=1;i<=m;i++) {155         read(x);read(y);read(val);read(cost[i]);156         add_edge1(x,y,val,cost[i]);157     }158     while(spfa_flow()) 159         MAX_FLOW+=max_flow();160     change();161     while(spfa_fee()) {162         int FLOW=MIN_fee();163         MIN_FEE+=FLOW*fee[n];164     }165     printf("%d %d\n",MAX_FLOW,MIN_FEE);166     return 0;167 }