2023 ICPC 南京站 E 题解

First Post:

Last Update:

根本不会。有点诈骗。

题意传送门：https://codeforces.com/gym/104821/problem/E

首先让最短路恰好增加 是个让人很摸不着头脑的问题。考虑进行转化，注意到这是在网格图上，可以考虑将最短路转化为对偶图的最小割。具体地，在每个 的小正方形中间那个面上建一个点，在最顶端小正方形的上方额外建一排点，当作源点，在最底端小正方形的下方额外建一排点，当作汇点。相邻点之间连边，边权为原图中垂直这两个点连线的那条边的边权，从第一列到最后一列的最短路就变成这张图的最小割。

现在要让最短路增加 ，也就是让对偶图的最小割（最大流）增加 。让最大流增加 ，其实可以变成一个费用流问题。假如对偶图中有一条边 ，我们就在费用流图中建两条边 与 。于是答案就是流量为 的费用最小的流（其中 为原图最短路）。

再求费用流时，因为 很大， 很小，可以先对费用为 的网络跑一遍 Dinic，然后再跑普通费用流，这样费用流部分就只用增广 次，这是官方题解做法，复杂度 。我直接写了个 Dijkstra 费用流，然后它就过了，复杂度上界是 ，但远远跑不满。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5,M = 2e6 + 5;
const int inf = 0x3f3f3f3f;

int n,m,cnt,K;
int id[N][N];
int a[N][N],b[N][N];
int tp[M],p1[M],p2[M];

namespace Flow {
	int fir[N],nxt[M],to[M],w[M],cst[M],ect = 1;
	inline void addedge(int u1,int v1,int w1,int c1) {
		nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;cst[ect] = c1;tp[ect] = 0;
	}
	inline void ins(int u1,int v1,int w1,int c1) { addedge(u1,v1,w1,c1);addedge(v1,u1,0,-c1);}
	int dis[N],h[N],vst[N],pw[N],pe[N];
	int tot;
	inline void Clr(int _n) {
		tot = _n;ect = 1;
		for(int i = 1;i <= tot;i++) fir[i] = h[i] = 0;
	}
	struct node {
		int id,dis;
		node(){}
		node(const int _id,const int _dis):id(_id),dis(_dis){}
		bool operator < (const node &rhs) const { return dis > rhs.dis;}
	};
	priority_queue<node> Q;
	bool Dijkstra(int S,int T) {
		for(int i = 1;i <= tot;i++) dis[i] = 1e9,vst[i] = 0;
		Q.emplace(S,dis[S] = 0);
		while(!Q.empty()) {
			int x = Q.top().id;Q.pop();
			if(vst[x]) continue;
			vst[x] = true;
			for(int i = fir[x],y;y = to[i],i;i = nxt[i])
				if(w[i] > 0 && dis[y] > dis[x] + cst[i] + h[x] - h[y])
					Q.emplace(y,dis[y] = dis[x] + cst[i] + h[x] - h[y]),pw[y] = x,pe[y] = i;
		}
		return dis[T] < 1e9;
	}
	int MCMF(int S,int T,int K) {
		int res = 0,D = 0,flow = 0;
		while(Dijkstra(S,T)) {
			for(int i = 1;i <= tot;i++) h[i] += dis[i];
			int f = 1e9;	
			for(int i = T;i != S;i = pw[i]) f = min(f,w[pe[i]]);
			if(h[T] != 0) f = min(f,D + K - flow);
			if(!f) break;
			for(int i = T;i != S;i = pw[i]) w[pe[i]] -= f,w[pe[i] ^ 1] += f;
			flow += f;res += h[T] * f;
			if(h[T] == 0) D = flow;
		}
		return res;
	}
}


inline void work() {
	cin >> n >> m >> K;
	cnt = 0;
	for(int i = 0;i <= n;i++) for(int j = 1;j < m;j++) id[i][j] = ++cnt;
	int S = cnt + 1,T = cnt + 2;cnt += 2;
	Flow::Clr(cnt);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j < m;j++) {
			cin >> a[i][j];
			int u = id[i - 1][j],v = id[i][j];
			Flow::ins(u,v,a[i][j],0);
			Flow::ins(u,v,inf,1);
			tp[Flow::ect] = 1;p1[Flow::ect] = i;p2[Flow::ect] = j;
			Flow::ins(v,u,a[i][j],0);
			Flow::ins(v,u,inf,1);
			tp[Flow::ect] = 1;p1[Flow::ect] = i;p2[Flow::ect] = j;
		} 
	for(int i = 1;i < n;i++)
		for(int j = 1;j <= m;j++) {
			cin >> b[i][j];
			if(j == 1 || j == m) continue;
			int u = id[i][j - 1],v = id[i][j];
			Flow::ins(u,v,b[i][j],0);Flow::ins(u,v,inf,1);
			tp[Flow::ect] = 2;p1[Flow::ect] = i;p2[Flow::ect] = j;
			Flow::ins(v,u,b[i][j],0);Flow::ins(v,u,inf,1);
			tp[Flow::ect] = 2;p1[Flow::ect] = i;p2[Flow::ect] = j;
		}
	for(int i = 1;i < m;i++) Flow::ins(S,id[0][i],inf,0),Flow::ins(id[n][i],T,inf,0);
	int num = Flow::MCMF(S,T,K);
	cout << num << endl;
	for(int i = 1;i <= Flow::ect;i++)
		if(tp[i] > 0) {
			assert(Flow::w[i] >= 0);
			if(tp[i] == 1) a[p1[i]][p2[i]] += Flow::w[i];
			else b[p1[i]][p2[i]] += Flow::w[i];
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j < m;j++)
			cout << a[i][j] << (j == m - 1 ? '\n' : ' ');
	for(int i = 1;i < n;i++)
		for(int j = 1;j <= m;j++)
			cout << b[i][j] << (j == m ? '\n' : ' ');
}
int main() {
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
≡