QOJ6681 Triangle City 题解

First Post:

Last Update:

咋每次碰到欧拉路就啥都不会呢？

题意：给一张带边权的三角形网格图，求 到 不经过重复边的最长路。

首先有一个直觉就是大部分的边都会被走过，那不会被走过的边长什么样子呢？

事实上，对于任意一条从 到 的简单路径，我们都能构造出恰好不经过这条路径的方案，因为原图上所有点的度数都是偶数，删去这条路径后， 与 的度数为奇数，其余点度数为偶数，那么一定存在一条从 到 的欧拉路径。就能构造了。

那么要让剩下的部分最长，我们当然找一条从 到 的最短路删了。

于是就做完了，不知道三角形不等式的限制条件有什么用。

由这题可见，欧拉路算法往往出现在一些情况复杂的构造当中，如果我们能掌握关于图中每个点度数的信息，就可以尝试找欧拉路来解决问题。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 3e2 + 5,V = N * N,M = 8 * N * N;
int n;
int Id[N][N],tot,px[V],py[V];

int fir[V],nxt[M],to[M],w[M],ect = 1;
long long dis[V];
bool vst[V];
int pv[V],pe[V],sgn[M];
inline void addedge(int u1,int v1,int w1) {
	nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;sgn[ect] = 0;
}
inline void ins(int u1,int v1,int w1) { addedge(u1,v1,w1);addedge(v1,u1,w1);}
struct node {
	int id;long long dis;
	node(){}
	node(const int _id,const long long _dis):
		id(_id),dis(_dis){}
	bool operator < (const node &rhs) const { return dis > rhs.dis;}
};

inline void Dijkstra(int S) {
	for(int i = 1;i <= tot;i++) dis[i] = 1e18,vst[i] = 0;
	priority_queue<node> Q;
	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(dis[y] > dis[x] + w[i])
				Q.emplace(y,dis[y] = dis[x] + w[i]),pv[y] = x,pe[y] = i;
	}
}
int stk[M],top;
void Euler(int x) {
	for(int i = fir[x],y;y = to[i],i;i = fir[x]) {
		fir[x] = nxt[i];
		if(sgn[i]) continue;
		sgn[i] = sgn[i ^ 1] = true;
		Euler(y);
	}
	stk[++top] = x;
}
inline void work() {
	for(int i = 1;i <= tot;i++) fir[i] = 0;
	for(int i = 1;i <= ect;i++) sgn[i] = 0;
	tot = top = 0;ect = 1;
	cin >> n;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= i;j++) Id[i][j] = ++tot,px[tot] = i,py[tot] = j;
	long long Sum = 0;
	for(int i = 1;i < n;i++)
		for(int j = 1,x;j <= i;j++)
			cin >> x,Sum += x,ins(Id[i][j],Id[i + 1][j],x);
	for(int i = 1;i < n;i++)
		for(int j = 1,x;j <= i;j++)
			cin >> x,Sum += x,ins(Id[i][j],Id[i + 1][j + 1],x);
	for(int i = 1;i < n;i++)
		for(int j = 1,x;j <= i;j++)
			cin >> x,Sum += x,ins(Id[i + 1][j],Id[i + 1][j + 1],x);
	Dijkstra(Id[1][1]);
	for(int now = Id[n][n];now != Id[1][1];now = pv[now]) 
		sgn[pe[now]] = sgn[pe[now] ^ 1] = true;
	cout << Sum - dis[Id[n][n]] << endl;
	Euler(Id[1][1]);
	cout << top << endl;
	for(int i = top;i >= 1;i--) 
		cout << px[stk[i]] << ' ' << py[stk[i]] << (i == 1 ? '\n' : ' ');
}
int main() {
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
≡