「bzoj4669」抢夺 - 二分+费用流 | Bill Yang's Blog

「bzoj4669」抢夺 - 二分+费用流

题目大意

    大战将至, 美国决定实行计划经济。美国西部总共有$N$个城市,编号为$0\rightarrow N−1$,以及$M$条道路,道路是单向的。其中城市$0$是一个大城市,里面住着$K$个人,而城市$N−1$是一个农业城市。现在所有城市$0$的居民都需要到城市$N−1$去领取食物。由于担心体力不支,所以居民都会采取开车的形式出行。但道路不是无限宽的,对于一条道路,会有$c_i$的限制,表示在同一天内,最多只能有$c_i$辆车同时在这条道路上行驶。一条道路的长度为$1$,每辆车的行驶速度也可以假定为$1$每天。城市$N−1$会在每个居民都到达后马上开始发放食物。现在Reddington想知道,假如在最优安排下,居民最早能在多少天后领到食物。假如没有居民那就不需要发放食物,默认为第$0$天。


题目分析

考虑二分答案$ans$。
考虑第一波最先走的人,他们肯定沿着各种途径前往目标结点,因此后一波走的人路径与前一波人完全相同。
因此我们可以根据第一次的增广计算出在$ans$天内到达的人数:

其中$dist[]$是残余网络最短路,$a[]$是可增广量。
若$num\ge k$,则$ans$天是可行的。

因为二分与网络流独立,因此可以先做一次网络流,然后再二分。

至于退流造成的影响。
考虑退流所获得的贡献与退流的意义所对应的贡献,列出式子发现贡献和是相同的,故退流没有影响。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
#define mp make_pair
#define pii pair<int,int>
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005;
struct Edge {
int from,to,cap,flow,cost;
Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};
vector<pii> A;
struct MinimumCost_MaximumFlow {
int n,m;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn];
int a[maxn],dist[maxn],path[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v,int f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bellmanford(int s,int t) {
for(int i=1; i<=n; i++)dist[i]=INT_MAX;
memset(inque,0,sizeof(inque));
queue<int>Q;
Q.push(s);
dist[s]=path[s]=0;
a[s]=INT_MAX;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id];
int Next=e.to;
if(e.cap>e.flow&&dist[Next]>dist[Now]+e.cost) {
dist[Next]=dist[Now]+e.cost;
path[Next]=id;
a[Next]=min(a[Now],e.cap-e.flow);
if(!inque[Next]) {
Q.push(Next);
inque[Next]=1;
}
}
}
}
if(dist[t]==INT_MAX)return false;
for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
edges[path[Now]].flow+=a[t];
edges[path[Now]^1].flow-=a[t];
}
return true;
}
void maxflow(int s,int t) {
while(bellmanford(s,t))A.push_back(mp(dist[t],a[t]));
}
} mcmf;
int n,m,k,x[5005],y[5005],v[5005];
bool Check(int ans) {
LL num=k;
for(pii x:A)num-=(LL)(ans-x.first+1)*x.second;
return num<=0;
}
int main() {
while(~scanf("%d%d%d",&n,&m,&k)) {
for(int i=1; i<=m; i++) {
x[i]=Get_Int()+1;
y[i]=Get_Int()+1;
v[i]=Get_Int();
}
if(!k) {
puts("0");
continue;
}
mcmf.init(n);
for(int i=1; i<=m; i++)mcmf.AddEdge(x[i],y[i],v[i],1);
A.clear();
mcmf.maxflow(1,n);
int Left=1,Right=n+k;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid))Right=mid-1;
else Left=mid+1;
}
if(Left==n+k+1)puts("No solution");
else printf("%d\n",Left);
}
return 0;
}
0%