网络流24题专题1·较简单的费用流

$\rm{Preface}~$

关于网络流,一直是我的一个阴影……因为去年暑假,大家都会而网络流,我因为觉得这个算法没意思就没学,结果rqy来给我们考试网络流那题被全场打爆了——除了我qaq。

于是决定开始做这些题,每道题都会标注我看题解程度多少,如果太高的话会被自己嫌弃的qaq……希望自己能争气一点。

$\rm{0x01}$ 运输问题

传送门:https://www.luogu.org/problemnew/show/P4015

看了,程度大概80%……呃我知道这个题不难,但是毕竟我上次写费用流可是几百年之前了啊……qaq

其实就是
$$
S\stackrel{f = a_i,c = 0}{\longrightarrow}i \stackrel{f = Inf,c = c_{i,j}}{\longrightarrow}j \stackrel{f = b_j,c=0}{\longrightarrow}T
$$

其中$i$代表仓库的编号,$j$代表商店的编号,建完图跑费用流即可。

由于SPFA死了,所以就一直用$dijk$做费用流,只不过难背一点……然后第二问的话就把权值取负重新做一下费用流就好。

总结一下,这个题似乎是比较裸的费用流的题了?一般费用流大概都是用来求解最优化问题的吧qwq……

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
struct Edge{
int to, next, f, c ;
}E[MAXN] ; int head[MAXN], cnt = -1 ;
int S, T, N, M, dist[MAXN], i, j, k, t[MAXN], x ;
struct node{
int dist, num ;
bool operator <(const node & now) const{return dist > now.dist ; }
}; priority_queue<node> q ; bool vis[MAXN] ; int Last[MAXN], F[MAXN], H[MAXN], Pre[MAXN], MAX_C ;

inline void Add(const int &u, const int &v, const int &f, const int& c){
E[++ cnt].to = v, E[cnt].c = c, t[cnt] = f ;
E[cnt].f = f, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].c = -c, t[cnt] = 0 ;
E[cnt].f = 0, E[cnt].next = head[v], head[v] = cnt ;
}
inline bool dijkstra(){
q.push((node){0, S}) ; vis[S] = dist[S] = 0, F[0] = Inf ;
for (i = 1 ; i <= T ; ++ i) dist[i] = F[i] = Inf, vis[i] = 0 ;
while (!q.empty()){
node now = q.top() ; q.pop() ;
int fr = now.num, sec = now.dist ; if (vis[fr]) continue ;
for (vis[fr] = 1, k = head[fr] ; k != -1 ; k = E[k].next){
int nowc = sec + E[k].c + H[fr] - H[to(k)] ;
if (E[k].f > 0 && !vis[to(k)] && dist[to(k)] > nowc){
dist[to(k)] = nowc, q.push((node){dist[to(k)], to(k)}) ;
F[to(k)] = min(F[fr], E[k].f), Pre[to(k)] = fr, Last[to(k)] = k ;
}//!!!!!
}
}
return dist[T] < Inf ;
}
void MCMF(int qwq){
int _Ed ; MAX_C = 0 ;
while (dijkstra()){
_Ed = T, MAX_C += (dist[T] - H[S] + H[T]) * F[T] ;
while(_Ed != S) E[Last[_Ed]].f -= F[T], E[Last[_Ed] ^ 1].f += F[T], _Ed = Pre[_Ed] ;
for (i = 0 ; i <= T ; ++ i) H[i] += dist[i] ; /* cout << MAX_C << endl ; */
}
cout << MAX_C * qwq << endl ;
}
int main(){
cin >> N >> M, S = 0 ;
T = N + M + 1, memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &x), Add(S, i, x, 0) ;
for (i = N + 1 ; i <= N + M ; ++ i) scanf("%d", &x), Add(i, T, x, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = N + 1 ; j <= N + M ; ++ j)
scanf("%d", &x), Add(i, j, Inf, x) ;
// for (i = 0 ; i <= cnt ; ++ i) printf("%d %d %d\n", E[i].to + 1, E[i].f, E[i].c) ;
MCMF(1) ; for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i], E[i].c = -E[i].c ; MCMF(-1) ; return 0 ;
}

$\rm{0x02~}$ 分配问题

传送门:https://www.luogu.org/problemnew/show/P4014

这道题由于实在太水了,所以没有看题解(窃喜

其实就是建$2n$个点,然后$i \stackrel{f = Inf,c = base_{i,j}}{\longrightarrow} j$就连完了。

不得不说…建边真的是太水了,太水了,qaq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
此处是dijkstra……
void MCMF(int qwq){
int _Ed ; MAX_C = 0 ;
while (dijkstra()){
_Ed = T, MAX_C += (dist[T] - H[S] + H[T]) * F[T] ;
while(_Ed != S) E[Last[_Ed]].f -= F[T], E[Last[_Ed] ^ 1].f += F[T], _Ed = Pre[_Ed] ;
for (i = 0 ; i <= T ; ++ i) H[i] += dist[i] ; /* cout << MAX_C << endl ; */
}
cout << MAX_C * qwq << endl ;
}
int main(){
memset(head, -1, sizeof(head)) ;
cin >> N ; S = 0, T = N << 1 | 1 ;
for (i = 1 ; i <= N ; ++ i) Add(S, i, 1, 0) ;
for (i = N + 1 ; i <= N + N ; ++ i) Add(i, T, 1, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = N + 1 ; j <= N + N ; ++ j)
cin >> x, Add(i, j, Inf, x) ;
MCMF(1) ; for (i = 0 ; i <= cnt ; ++ i) E[i].c = -E[i].c, E[i].f = t[i] ; MCMF(-1) ; return 0 ;
}

$\rm{0x03}~$数字梯形问题

传送门:https://www.luogu.org/problemnew/show/P4013

看题解:$90\%$+…我是真没见过这种建边方式啊喂,并且我一开始建的边很迷…我没有看到,呃,换句话说,我看到了然后忘了,一个数只能向正下方和右下方走……

第一问·完全不相交的路径

我真是要菜死了,题解里面说”拆点已经是烂大街的$trick$了”,我:???

大概就是每个点拆成两个点,原因是我们需要把点上的限制转化成边上的限制,所以需要进行拆点,然后对于某个点和它的副本连一条$f=1,c=-base[x]$的边,毕竟是求最大值。然后$S$和最顶上的连$f=1,c=0$的边,$T$和最下面一层连$f=1,c=0$,就完了。

第二问 · 边不相交的路径

我们考虑此时其实是删除了点的限制,那么我们就将每个点和自己的副本之间的边容量改成$Inf$,并把$T$与最底下的所有点的容量扩为$Inf$即可。注意后半部分的扩容,其目的在于防止中间节点的扩容被限制。

第三问 · 随便的路径

既然都随便了,就直接把所有的边都设置成$Inf$,但是显然的是我们不能扩$S$连出去的边。

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
inline bool dijk(){
for (i = 0 ; i <= tot + 2 ; ++ i)
dist[i] = F[i] = Inf, vis[i] = 0 ;
dist[S] = 0, q.push((Node){S, 0}) ;
while (!q.empty()){
Node now = q.top() ; q.pop() ;
int num = now.num, dis = now.dist ; if (vis[num]) continue ;
for (int k = head[num] ; k != -1 ; k = E[k].next){
int DIS = E[k].c + H[num] - H[to(k)] + dis ;
if (DIS < dist[to(k)] && !vis[to(k)] && E[k].f)
F[to(k)] = min(F[num], E[k].f), dist[to(k)] = DIS,
q.push((Node){to(k), DIS}), Pre[to(k)] = num, Last[to(k)] = k ;
}
}
return dist[T] < Inf ;
}
inline void MCMF(){
Ans = 0 ;
while (dijk()){
_End = T, Ans += (dist[T] - H[S] + H[T]) * F[T] ;
while (_End) E[Last[_End]].f -= F[_End], E[Last[_End] ^ 1].f += F[_End], _End = Pre[_End] ;
for (i = 0 ; i <= tot + 2 ; ++ i) H[i] += dist[i] ; /*cout << -Ans << endl ;*/
}
}
int L1, R1, L ;
int main(){
memset(head, -1, sizeof(head)) ;
cin >> M >> N ; S = 0, T = 1 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
cin >> base[i][j], Id[i][j] = (tot += 2) ;
for (i = 1 ; i <= M ; ++ i) Add(S, Id[1][i], 1, 0) ; L = cnt + 1 ;
for (L1 = cnt + 1, i = 1 ; i <= N + M ; ++ i) Add(Id[N][i] + 1, T, 1, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
Add(Id[i][j], Id[i][j] + 1, 1, -base[i][j]) ; R1 = cnt ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
if (i < N) Add(Id[i][j] + 1, Id[i + 1][j], 1, 0), Add(Id[i][j] + 1, Id[i + 1][j + 1], 1, 0) ;
MCMF() ; cout << -Ans << endl ;
for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i] ;
for (i = L1 ; i < R1 ; i += 2) E[i].f = Inf ;
for (i = L1 + 1 ; i <= R1 ; i += 2) E[i].f = 0 ;
MCMF() ; cout << -Ans << endl ;
for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i] ;
for (i = L ; i < cnt ; i += 2) E[i].f = Inf ;
for (i = L + 1 ; i <= cnt ; i += 2) E[i].f = 0 ;
MCMF() ; cout << -Ans << endl ; return 0 ;
/* 以下是错误的建边
for (i = 1 ; i <= M ; ++ i)
cin >> base[++ tot], Add(S, tot, 1, -base[tot]) ;
for (i = 1 ; i < N ; ++ i)
for (j = 1 ; j <= M + i ; ++ j){
cin >> base[++ tot] ; int sd = (2 * M + i - 2) * (i - 1) / 2 + 1 ;
for (int k = sd ; k <= (2 * M + i - 1) * i / 2 ; ++ k) Add(k, tot, Inf, -base[tot]) ;
}
for (T = tot + 1, i = tot - (N + M - 1) + 1 ; i <= tot ; ++ i) Add(i, T, 1, 0) ; ++ tot, MCMF() ; cout << -Ans << endl ; */
/*MCMF() ; cout << -Ans << endl ; */
}

嗯,大概这三个题就先分成一组吧!

-------------本文结束感谢您的阅读-------------