题目链接
题意
给你无向图每个点的度数, 问是否存在唯一解, 存在输出唯一解, 多解输出两个, 无解输出IMPOSSIBLE
思路
这里用到了 Havel-Hakimi定理, 实际上就是按照度数构图的一种贪心策略. 这样能判断出来一个解或无解, 多解的情况, 只要在比较构图时最后面两个点的当前度数一样, 那么选其一都是可行的, 但是选其一的情况有保证了另外一个肯定没有连上, 所以能找到其它解.
代码
#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
struct Node{
int val, pos;
}d[105], b[105];
pair<int, int> res1[10005], res2[10005];
int cnt1, cnt2;
bool compare(Node x, Node y){
return x.val > y.val;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int n;
while (~scanf("%d", &n)){
bool noans = false;
cnt1 = cnt2 = 0;
for (int i = 1; i <= n; i++){
scanf("%d", &d[i].val);
d[i].pos = i;
if (d[i].val > n - 1) noans = true;
b[i] = d[i];
}
sort(d + 1, d + n + 1, compare);
bool isunique = true;
while (!noans){
if (d[1].val == 0) break;
for (int i = 2; i < 2 + d[1].val; i++){
d[i].val--;
res1[cnt1++] = make_pair(d[1].pos, d[i].pos);
if (d[i].val < 0){
noans = true;
break;
}
}
if (d[2 + d[1].val].val - d[1 + d[1].val].val == 1){
isunique = false;
}
d[1].val = 0;
sort(d + 1, d + n + 1, compare);
}
if (noans){
printf("IMPOSSIBLE\n");
continue;
}
if (isunique){
printf("UNIQUE\n");
}
else{
printf("MULTIPLE\n");
for (int i = 1; i <= n; i++){
d[i] = b[i];
}
sort(d + 1, d + n + 1, compare);
bool first = true;
while (d[1].val != 0){
for (int i = 2; i < 1 + d[1].val; i++){
d[i].val--;
res2[cnt2++] = make_pair(d[1].pos, d[i].pos);
}
if (first && d[1 + d[1].val].val == d[2 + d[1].val].val){
first = false;
d[2 + d[1].val].val--;
res2[cnt2++] = make_pair(d[1].pos, d[2 + d[1].val].pos);
}
else{
d[1 + d[1].val].val--;
res2[cnt2++] = make_pair(d[1].pos, d[1 + d[1].val].pos);
}
d[1].val = 0;
sort(d + 1, d + n + 1, compare);
}
}
printf("%d %d\n", n, cnt1);
for (int i = 0; i < cnt1; i++){
printf("%d ", res1[i].first);
}
printf("\n");
for (int i = 0; i < cnt1; i++){
printf("%d ", res1[i].second);
}
printf("\n");
if (!isunique){
printf("%d %d\n", n, cnt2);
for (int i = 0; i < cnt2; i++){
printf("%d ", res2[i].first);
}
printf("\n");
for (int i = 0; i < cnt2; i++){
printf("%d ", res2[i].second);
}
printf("\n");
}
}
}