CF1416F 题解

First Post:

Last Update:

自己做出来的，很厉害啊！

首先考虑分析问题的结构。每个 只有一条出边，那最终形成的肯定是若干个内向基环树。对于环上的点，岂能到达的就是环中的所有点，所以一个环上的点的 都必须相等。对于树上的点，其能到达的是一条祖先链加上其对应环中的点。因为 中的元素都是正整数，所以其父亲的 应该严格小于自己。

然后缩小决策范围。注意到内向基环树中的所有环都是偶环，而将偶环中每相邻两个元素拆出来，形成若干个长度为 的环，是不影响原来构造的正确性的。所以我们只需考虑所有内向基环树中环长都为 的情况。

假设我们已经选出了在环上的点集 ，那 需要满足什么条件呢？首先 能被划分成若干个点对，使得每个点对相邻且 相等（即若干个长度为 的环）；其次，对于 的点，由 向 连一条边，表示 能成为 的父亲。其它方向同理。那么所有入度为 的点必须被 包含，而入度 的点不一定要被 包含。因为这样连边形成的图肯定是 DAG，可以通过在 DAG 上每次删去入度为 的点来归纳证明。

容易发现，如果将 按照 的奇偶性划分成两个部分，相邻且 相等的点之间连边，那么 就是这张二分图上的一个匹配。我们对这个匹配的限制就是必须覆盖某些点。这是经典的有源汇上下界可行流问题，容易用 dinic 算法解决。

在确定了点集 后，其余点的构造也容易得到，只需沿着 “ 能成为 的父亲" 这种边 dfs 即可。

具体构造见代码，写得比较丑。时间复杂度是二分图匹配复杂度，因为 ，时间复杂度为 。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,m;
inline int Plc(int i,int j) { return (i - 1) * m + j;}
inline int vaild(int i,int j) { return i >= 1 && i <= n && j >= 1 && j <= m;}
vector<int> sum[N];

namespace Flow {
	const int M = 2e6 + 5;
	int fir[N],nxt[M],to[M],w[M],Id[M],ect = 1;
	inline void addedge(int u1,int v1,int w1,int id1) {
		nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;Id[ect] = id1;
	}
	inline void ins(int u1,int v1,int w1,int id1) { addedge(u1,v1,w1,id1);addedge(v1,u1,0,0);}
	int dep[N],cur[N],tot;
	inline void Clr(int _n) {
		tot = _n;ect = 1;
		for(int i = 1;i <= tot;i++) fir[i] = 0;
	}
	inline bool bfs(int S,int T) {
		for(int i = 1;i <= tot;i++) dep[i] = 1e9,cur[i] = fir[i];
		queue<int> Q;Q.push(S);dep[S] = 0;
		while(!Q.empty()) {
			int x = Q.front();Q.pop();
			for(int i = fir[x],y;y = to[i],i;i = nxt[i])
				if(w[i] && dep[y] > dep[x] + 1)
					dep[y] = dep[x] + 1,Q.push(y);
		}
		return dep[T] < 1e9;
	}
	int dfs(int u,int t,int limit) {
		if(u == t || !limit) return limit;
		int flow = 0,f;
		for(int i = cur[u],v;v = to[i],i;i = nxt[i]) {
			cur[u] = i;
			if((dep[v] == dep[u] + 1) && w[i] && (f = dfs(v,t,min(limit,w[i])))) {
				flow += f;
				limit -= f;
				w[i] -= f;
				w[i ^ 1] += f;
				if(!limit) break;
			}
		}
		return flow;
	}
	inline int dinic(int S,int T) {
		int res = 0;
		while(bfs(S,T)) res += dfs(S,T,2e9);
		return res;
	}
}
int A[N];char B[N];
// vector<int> A[N];vector<char> B[N];
bool vst[N];
const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};
bool mst[N]; // 必须是环点
int G[N];
int flw[N];

inline void Insedge(int u1,int v1,int l1,int r1,int id1) {
	flw[v1] += l1;flw[u1] -= l1;
	if(l1 < r1) Flow::ins(u1,v1,r1 - l1,id1);
}
bool incirc[N];

void dfs(int x,int y) {
	vst[Plc(x,y)] = true;
	for(int k = 0;k < 4;k++) if((G[Plc(x,y)] >> k) & 1) {
		int tx = x + dx[k],ty = y + dy[k];
		if(!vaild(tx,ty) || incirc[Plc(tx,ty)] || vst[Plc(tx,ty)]) continue;
		A[Plc(tx,ty)] = sum[tx][ty] - sum[x][y];
		if(k == 0) B[Plc(tx,ty)] = 'D';
		if(k == 1) B[Plc(tx,ty)] = 'R';
		if(k == 2) B[Plc(tx,ty)] = 'L';
		if(k == 3) B[Plc(tx,ty)] = 'U';
		dfs(tx,ty);
	}
}
inline void Main() {
	cin >> n >> m;
	for(int i = 1;i <= n;i++) sum[i].resize(m + 1);
	int num = n * m;
	for(int i = 1;i <= num;i++) vst[i] = mst[i] = incirc[i] = A[i] = B[i] = G[i] = 0;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin >> sum[i][j];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) {
			mst[Plc(i,j)] = 1;
			for(int k = 0;k < 4;k++) {
				int tx = i + dx[k],ty = j + dy[k];
				if(!vaild(tx,ty)) continue;
				if(sum[tx][ty] < sum[i][j]) mst[Plc(i,j)] = 0;
				if(sum[tx][ty] > sum[i][j]) G[Plc(i,j)] |= (1 << k);
			}
		}
	int S = num + 1,T = num + 2,SS = num + 3,TT = num + 4;
	Flow::Clr(num + 4);
	for(int i = 1;i <= num + 2;i++) flw[i] = 0;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) 
			if((i + j) & 1) Insedge(S,Plc(i,j),mst[Plc(i,j)],1,Plc(i,j));
			else Insedge(Plc(i,j),T,mst[Plc(i,j)],1,Plc(i,j));
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if((i + j) & 1) {
				for(int k = 0;k < 4;k++) {
					int tx = i + dx[k],ty = j + dy[k];
					if(vaild(tx,ty) && sum[i][j] == sum[tx][ty]) Flow::ins(Plc(i,j),Plc(tx,ty),1,0);
				}
			}
	for(int i = 1;i <= num + 2;i++)
		if(flw[i] > 0) Flow::ins(SS,i,flw[i],0);
		else if(flw[i] < 0) Flow::ins(i,TT,-flw[i],0);
	Flow::ins(T,S,2e9,0);
	Flow::dinic(SS,TT);
	for(int e = Flow::fir[SS];e;e = Flow::nxt[e]) if(Flow::w[e]) return puts("NO"),void();
	Flow::w[Flow::ect] = Flow::w[Flow::ect ^ 1] = 0;
	for(int e = Flow::fir[SS];e;e = Flow::nxt[e])
		Flow::w[e] = Flow::w[e ^ 1] = 0;
	for(int e = Flow::fir[TT];e;e = Flow::nxt[e])
		Flow::w[e] = Flow::w[e ^ 1] = 0;
	Flow::dinic(S,T);
	for(int i = 1;i <= Flow::ect;i++)
		if(Flow::Id[i] > 0 && !Flow::w[i]) incirc[Flow::Id[i]] = true;
	for(int i = 1;i <= num;i++) if(mst[i]) incirc[i] = true;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) if((i + j & 1) && incirc[Plc(i,j)]) {
		for(int e = Flow::fir[Plc(i,j)];e;e = Flow::nxt[e])
			if(Flow::to[e] >= 1 && Flow::to[e] <= num && !Flow::w[e]) {
				int id = Plc(i,j),pp = Flow::to[e];A[Plc(i,j)] = 1;A[pp] = sum[i][j] - 1;
				if(pp == id - 1) B[id] = 'L',B[pp] = 'R';
				if(pp == id + 1) B[id] = 'R',B[pp] = 'L';
				if(pp == id - m) B[id] = 'U',B[pp] = 'D';
				if(pp == id + m) B[id] = 'D',B[pp] = 'U';
			}
	}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(incirc[Plc(i,j)] && !vst[Plc(i,j)]) dfs(i,j);
	puts("YES");
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			printf("%d%c",A[Plc(i,j)]," \n"[j == m]);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			printf("%c%c",B[Plc(i,j)]," \n"[j == m]);
}
int main() {
	int T;
	cin >> T;
	while(T--) Main();
	return 0;
}
≡