bzoj1834: [ZJOI2010]network 网络扩容

1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 2677 Solved: 1359
[Submit][Status][Discuss]

Description

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

Input

输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

Output

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

Sample Input

5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1

Sample Output

13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define N 102333
 5 #include<queue>
 6 #define inf 2147483647
 7 using namespace std;
 8 inline int read(){
 9      int x=0; char ch=getchar();
10      while(ch<'0'||ch>'9') ch=getchar();
11      while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
12      return x;
13 }
14 struct node{
15      int w,to,next,c,from;
16 }e[N<<1],E[N<<1];
17 int head[N],dis[N],from[N],i,j,zs1,zs2,zs3,zs4,tot=1,t,anss,m,n,sum,flow;
18 bool vis[N];
19 int tot1,tot2,num[N][2];
20 inline void ins(int u,int v,int w,int cost){
21      e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;
22 }
23 inline bool spfa(){
24      for(int i=0;i<=t;i++) dis[i]=inf; vis[0]=1; dis[0]=0; queue<int>q; q.push(0);
25      while(!q.empty()) {
26           int x=q.front(); q.pop();
27           for(int k=head[x];k;k=e[k].next)
28             if (dis[x]+e[k].c<dis[e[k].to] && e[k].w>0) {
29                     from[e[k].to]=k;
30                 dis[e[k].to]=dis[x]+e[k].c;
31                 if(!vis[e[k].to]) {
32                      vis[e[k].to]=1; q.push(e[k].to);
33                 }
34             }
35           vis[x]=0;
36      }
37      if(dis[t]==inf) return 0;else return 1;
38 }
39 inline bool bfs(){
40      for(i=0;i<=t;i++) dis[i]=-1; queue<int>q; q.push(1); dis[1]=0;
41      while(!q.empty()) {
42           int x=q.front(); q.pop();
43           for(int k=head[x];k;k=e[k].next) 
44              if(dis[e[k].to]<0 && e[k].w>0) {
45                    dis[e[k].to]=dis[x]+1; q.push(e[k].to);
46              }
47      }
48      if(dis[t]>0) return 1;else return 0;
49 }
50 int find(int x,int low){
51      if(x==t) return low;
52      int delta=low,now;
53      for(int k=head[x];k;k=e[k].next) 
54        if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 
55            now=find(e[k].to,min(e[k].w,delta));
56            e[k].w-=now; e[k^1].w-=now;   delta-=now;
57            if(!delta) return low;
58         } 
59      dis[x]=-1;
60      return low-delta;
61 }
62 inline void run() {
63      int x=inf;
64      for(int i=from[t];i;i=from[e[i].from]) x=min(x,e[i].w);
65      for(int i=from[t];i;i=from[e[i].from]) {
66          anss+=e[i].c*x;e[i].w-=x; e[i^1].w+=x;
67      }
68 }
69 int main () {
70      n=read(); int road=read();m=read(); t=n;
71      for(i=1;i<=road;i++) {
72           zs1=read(),zs2=read(),zs3=read(),zs4=read();
73           ins(zs1,zs2,zs3,0); ins(zs2,zs1,0,0); num[++tot1][0]=tot-1,num[tot1][1]=zs3;
74           E[++tot2].from=zs1; E[tot2].to=zs2; E[tot2].c=zs4;
75      }
76      while(bfs()){
77           while(sum=find(1,inf)) flow+=sum;
78      }
79      printf("%d ",flow);
80      for(i=1;i<=tot1;i++) {
81           e[num[i][0]].w=num[i][1]; e[num[i][0]^1].w=0;
82      }
83      int u,v,cost;
84      ins(0,1,flow+m,0),ins(1,0,0,0);
85      for(i=1;i<=tot2;i++) {
86           u=E[i].from,v=E[i].to,cost=E[i].c;
87           ins(u,v,inf,cost); ins(v,u,0,-cost);
88      }
89      while(spfa()) run(); 
90      printf("%d",anss); 
91 }

View Code