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
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
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
HINT
Source
Day1
Solution
第一问就是最大流，第二问即费用流。
第一次跑最大流时建边费用为0，容量为输入容量C。第二次跑费用流时在原来的残余网络上再建边费用为扩容费用，容量为无限大。
再讲原来的N点连向新的T点容量为k，来满足增加流量为k。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=1010,M=21000; int n,m,k,tot,S,T,Next[M],head[N],tree[M],val[M],Cost[M],From[M],h[N],cur[N],Prev[N],FLOW,dis[N],Queue[N*2];k bool visit[N]; struct node{int x,y,z,d;}a[M]; namespace DINIC { bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); Queue[1]=S;h[S]=0; while (t!=w) { int u=Queue[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0) { int v=tree[i]; if (h[v]==-1) { Queue[++w]=v; h[v]=h[u]+1; } } } return h[T]!=-1; } int dfs(int u,int low) { if (u==T) return low; int used=0; for (int i=cur[u];i;i=Next[i]) { cur[u]=i; int v=tree[i]; if (val[i]>0&&h[v]==h[u]+1) { int w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=T;i++) cur[i]=head[i]; ans+=dfs(S,1<<29); } return ans; } } namespace MinCostFlow { void add(int x,int y,int z,int d) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; Cost[tot]=d; From[tot]=x; } void add_edge(int x,int y,int z,int d) { add(x,y,z,d); add(y,x,0,-d); } bool spfa() { memset(visit,0,sizeof(visit)); memset(Prev,0,sizeof(Prev)); for (int i=1;i<=T;i++) dis[i]=1<<29; int t=0,w=1; Queue[1]=S;visit[S]=1; dis[S]=0; while (t!=w) { t++; if (t>T*2) t=1; int u=Queue[t]; if (u==T) continue; visit[u]=0; for (int i=head[u];i;i=Next[i]) if (val[i]>0) { int v=tree[i]; if (dis[v]>dis[u]+Cost[i]) { dis[v]=dis[u]+Cost[i]; Prev[v]=i; if (!visit[v]) { w++; if (w>T*2) w=1; Queue[w]=v; visit[v]=1; } } } } return Prev[T]!=0; } int GetAns() { int Flow=1<<29,ans=0; for (int i=T;Prev[i];i=From[Prev[i]]) Flow=min(val[Prev[i]],Flow); FLOW+=Flow; for (int i=T;Prev[i];i=From[Prev[i]]) { ans+=Cost[Prev[i]]*Flow; val[Prev[i]]-=Flow; val[Prev[i]^1]+=Flow; } return ans; } int mcf() { int ans=0;FLOW=0; while (spfa()) ans+=GetAns(); return ans; } } int main() { using namespace DINIC; using namespace MinCostFlow; scanf("%d%d%d",&n,&m,&k); tot=1; S=1;T=n; for (int i=1;i<=m;i++) { scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].d); add_edge(a[i].x,a[i].y,a[i].z,0); } int ans=dinic(); printf("%d ",ans); for (int i=1;i<=m;i++) add_edge(a[i].x,a[i].y,1<<29,a[i].d); T++; add_edge(n,T,k,0); printf("%d\n",mcf()); return 0; } |
