POJ1659-Frogs' Neighborhood
这题乍一看非常简单，很快就假了个思路：将所有点遍历一遍，当前没有完成配对的，直接往后找同样没完成配对的点进行配对。这个思路怎么想都是对的，但就是一直WA。后面去POJ讨论区看了看，得知了hack数据
这个数据按照上面的思路输出的是NO，可以完成的前几组配对如下
但实际上这个数据是可以完成配对的，规则如下
之所以假思路不能求出这个答案，是因为它每次都让前面的点相互配，将前面的点配完了，后面的点就没得配了。为了避免这个问题，需要将点放进堆中，排序依据是点在当前还需要配的点的数量。每次取需要配的点的数量最多的点，然后依次取需要配的数量数量第二多、第三多…的点跟它配，配完为止。
为什么这么配可以得到正解？感性分析一下：如果每次将配对了的两个点间连上一条无向边，最终就会得到一张没有重边无向图。题目的输入数据限制了图中每一个点的度，一个点所处的图越大，它的度能满足限制的几率也就越大。也就是说要尽可能地构造出更大地图。由于各个点的度是一定的，为了构造出更大的图，就要尽可能地提高每个连通子图的稀疏度，也就是说：在点一定的情况下，他们之间所连的边应尽可能少，这样就能分出更多的边给外面的其它点。因此需要以上面所说的顺序选点。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
bool b[15][15];
int main()
{
int _, n, i, j, a;
scanf("%d", &_);
while (_--)
{
scanf("%d", &n);
priority_queue<pair<int, int> > pq;
for (i = 1; i <= n; i++)
{
scanf("%d", &a);
if (a)
pq.push(make_pair(a, i));
}
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
b[i][j] = 0;
bool flag = 0;
while (!pq.empty())
{
pair<int, int> px = pq.top();
pq.pop();
if (pq.empty())
{
flag = 1;
break;
}
stack<pair<int, int> > ps;
while (px.first)
{
if (pq.empty())
{
flag = 1;
break;
}
pair<int, int> pr = pq.top();
pq.pop();
if (b[pr.second][px.second])
{
if (pq.empty())
{
flag = 1;
break;
}
ps.push(pr);
continue;
}
b[pr.second][px.second] = b[px.second][pr.second] = 1;
pr.first--;
px.first--;
if (pr.first)
ps.push(pr);
}
if (flag)
break;
while (!ps.empty())
{
pq.push(ps.top());
ps.pop();
}
}
if (flag)
{
printf("NO\n\n");
continue;
}
printf("YES\n");
for (i = 1; i <= n; i++)
{
printf("%d", b[i][1]);
for (int j = 2; j <= n; j++)
printf(" %d", b[i][j]);
printf("\n");
}
printf("\n");
}
return 0;
}
|