UVa1116/LA2429 Puzzle

UVa1116/LA2429 Puzzle

• 题目链接
• 题意
• 分析
• 测试数据生成
• AC 代码

题目链接

   本题是2001年icpc欧洲区域赛中欧赛区的题目

题意

   Alice画了一个有n个顶点（编号从1到n）的凸多边形，并且还连了m条互不相交的对角线（端点接触不算相交）。她现在将所有这

m

+

n

m+n

m+n条无向边随机打乱顺序后，依次给出每条边的两个顶点，请Bob还原出原凸多边形，并将多边形的顶点按顺序输出（要求从1开始输出，第二个点需要是1的两个相邻顶点中最小的那个，之后输出点的顺序就明确了）。

分析

   按题目意思，首先想到找出图上最长的简单圈就是答案，奈何这其实是哈密顿圈，NP难的。

   还是要利用本题的特殊性另外想办法求解，本题目其实是要区分哪些边是原凸多边形的外边，哪些边是内边（对角线）。仔细分析选出的对角线互不相交这个条件，就能找到突破口：一定至少有两个顶点的度为2！

一定至少有两个顶点的度为2的证明：

   如果没有选出任何对角线，显然成立。否则，由于所有选出的对角线互不相交，用任意一条对角线将原图分割成两个凸多边形子图（此对角线成为两者的外边），如果有一者无选出的对角线，由其至少含三个顶点可知它至少有一个非分割线端点处度为2，那么如果两者均无选出的对角线，则结论成立。对于有选出的对角线的子图，按上述证明过程一定能继续递归至子图无选出的对角线，同样可知它至少有一个非对角线端点处度为2。

   求解过程和证明过程相似，维护优先级队列（以每个顶点的度排序）的过程中动态恢复凸多边形的外边。循环弹出队首顶点u后：如果顶点u的两条边已经恢复，则跳过；如果点u只剩下一条可选边，则对此边的两端点进行恢复，并且退出队列循环；顶点u有两条可选边（分别连向顶点a、b），则恢复顶点u并删除a和b连向u的可选边，将元组

(

u

,

a

,

b

)

(u,a,b)

(u,a,b)入栈，然后检查a、b之间是否有可选边，已经有则将元组(a,a的度)和(b,b的度)入队列，没有则a和b分别追加可选边(a,b)。队列循环退出后，将元组

(

u

,

a

,

b

)

(u,a,b)

(u,a,b)依次出栈，然后将顶点a已恢复的边(a,b)修改成(a,u)，将顶点b已恢复的边(b,a)修改成(b,u)。

测试数据生成

   uDebug上暂时没找打测试数据，这里给一份python写的生成测试数据的脚本

# -*- coding: utf-8 -*-
from random import random, shuffle
N = 10000
# N = 100
def check(d, n, x, y):
if y == x+1 or (y == n and x == 1):
return True
for u, v in d:
if v == u+1 or (v == n and u == 1) or u==x or u==y or v==x or v==y:
continue
a = x>u and x<v
b = y>u and y<v
if a != b:
return True
return False
if __name__ == '__main__':
with open('in.txt', 'w') as f:
f.write('10
')
for i in range(10):
f.write('
')
n = int(random()*(N-2)) + 3
m = int(random()*(n-2))
f.write(f'{n}
{m}
')
vetex, e, d, vis = [j for j in range(1, n+1)], [(n, 1)], [], [False for j in range((n+2)*(n+3))]
for j in range(1, n):
e.append((j, j+1))
for j in range(m):
u = int(random()*n) + 1
v = int(random()*(n-u)) + u + 1
while check(d, n, u, v) or vis[u*(n+1) + v]:
u = int(random()*n) + 1
v = int(random()*(n-u)) + u + 1
vis[u*(n+1) + v] = True
d.append((u, v))
for j in d:
e.append(j)
shuffle(vetex)
for u, v in e:
if random() < 0.5:
f.write(f'{vetex[u-1]} {vetex[v-1]} ')
else:
f.write(f'{vetex[v-1]} {vetex[u-1]} ')
f.write('
')

AC 代码

#include 
#include 
#include 
using namespace std;
#define N 10020
struct node {
int u, d;
bool operator< (const node& rhs) const{
return d > rhs.d;
}
};
int s[N][3], g[N][2], c[N], m, n; set<int> e[N];
void solve() {
cin >> n >> m;
for (int i=1; i<=n; ++i) c[i] = 0, e[i].clear();
for (int i=m+n; i>0; --i) {
int u, v; cin >> u >> v; e[u].insert(v); e[v].insert(u);
}
priority_queue<node> q; int h = 1, t = 0;
for (int i=1; i<=n; ++i) q.push({i, int(e[i].size())});
while (!q.empty()) {
node r = q.top(); q.pop(); int u = r.u;
if (c[u] == 2) continue;
if (e[u].size() == 1) {
int v = *e[u].begin(); g[u][c[u]++] = v; g[v][c[v]++] = u;
break;
}
set<int>::iterator it = e[u].begin(); int a = *it, b = *++it;
g[u][c[u]++] = a; g[u][c[u]++] = b; e[a].erase(u); e[b].erase(u);
if (!e[a].count(b)) e[a].insert(b), e[b].insert(a);
else q.push({a, int(e[a].size())}), q.push({b, int(e[b].size())});
s[t][0] = u; s[t][1] = a; s[t++][2] = b;
}
while (t--) {
int u = s[t][0], a = s[t][1], b = s[t][2];
g[a][0] == b ? g[a][0] = u : g[a][1] = u; g[b][0] == a ? g[b][0] = u : g[b][1] = u;
}
cout << 1; t = min(g[1][0], g[1][1]);
while (t != 1) {
cout << ' ' << t;
for (int i=0, v; i<2; ++i) if ((v = g[t][i]) != h) {
h = t; t = v; break;
}
}
cout << endl;
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
if (t) cout << endl;
}
return 0;
}