[UVA] 10471 - Can't be too GREEDY
Return of the Aztecs
| Problem I: | Can't be too GREEDY |
|
Time Limit: 5 seconds Memory Limit: 32 MB |
|
| Greed is all right, by the way I think greed is healthy. You can be greedy and still feel good about yourself. -- Ivan F. Boesky |
|
 |
 |
| Greedy coloring LOOSES | Greedy coloring WINS |
Okay, don't get confused. Greed is good and greed is bad -- we all know that pretty well. There are problems that can be solved quite easily with greedy approach, and there are problems where it fails.
Your mission, should you choose to accept it, is to show how bad a greedy approach can turn out to be. Given a number of colors, you'd have to show that a greedy approach can be as bad as to need all the colors given to color a tree.
Some useful information:
Any tree with more than one node can be properly colored using two colors only.
Proper Coloring: A coloring of a graph is proper if no two adjacent vertices receive the same color.
Greedy approach for graph coloring: Given a permutation (ordering) of the vertices, color each vertex using the least available proper color. Example: Let A be a vertex that is connected to B, C and D. B is connected to C and D. Given the permutation CDBA, you'd assign color 1 to C, 1 to D, 2 to B and 3 to A. Thus the greedy approach needs 3 colors (which is also optimal in this case) to color this graph.
Degree of a Vertex: The number of vertices connected to this vertex.
Input
There can be multiple test cases. For each test case you'd be given an integer K on a line. 1< K< 16, the number of colors the greedy approach would at least need to color the tree.
Output
For each input case you are to print the tree, followed by an ordering of the vertices that the greedy approach would follow. In the first line, print the number of vertices N and the number of edges M in one line. In the next M lines, print M edges. An edge is represented by two integers separated by a space. In the last line for the test case, print an ordering of the vertices such that the greedy approach would need at least K colors to color the tree properly. The vertex numbers are to be separated by spaces. Any valid solution will be accepted. However, you must strictly adhere to the following constraints.Constraints:
- Maximum degree for any vertex is K-1
- There can be at most 2^(K-1) vertices
- Vertices are to be numbered 1..N
Sample Input
2 4
Sample Output
2 1 1 2 1 2 8 7 1 2 2 3 2 5 4 3 1 6 8 1 6 7 8 4 7 5 3 6 2 1
Note: The image with the problem statement corresponds to the second sample output. A level order traversal on the tree would have allowed the greedy algorithm to use optimal coloring.
Problem setter: Monirul Hasan (Tomal), CSE Dept, Southeast University, Bangladesh
"Academic activities comes first and then comes the extra curricular activities like participating in programming contests, this message should be clear to all" -- some wise men would say to the contestants. But a contestant should be wise enough to safely ignore this message and would be ready to pay whatever prices are to be paid for ignoring the message. The wise contestant would say, "It is the contests that made me learn what I know, the academic activities have left little contribution there."
題目描述：
// 前面在描述如何使用 greedy 策略得到的最少著色數方式
// 每次著新的點時，先看附近有圖哪些顏色，盡可能挑一個使用且不重複的顏色
// 真的不行再增加一個顏色。
由於這種策略上，跟你選擇的圖色順序有關，如果順序好就容易得到最少著色數。
現在要求，隨便給定一棵樹和你所選擇的著色順序，根據 greedy 策略，
恰好得到 K 的著色數。
其中這棵樹的點數最多為 2^(K-1)，每個點的 degree 最多為 K-1。
題目解法：
遞迴結構
對於一個需要 K 種顏色的樹來說，根節點肯定接有 K-1 不同顏色的子節點，
而這些子節點又恰好由 K-1 種顏色的著色子樹。
// 稍微用數學歸納法計算點數，不超過 2^(K-1) 個節點
#include <stdio.h>
#include <vector>
using namespace std;
int node;
vector<int> C[20];
int dfs(int color) {
int x = ++ node;
C[color].push_back(x);
for(int i = 1; i < color; i++)
printf("%d %d\n", x, dfs(i));
return x;
}
int main() {
int K, i, j;
while(scanf("%d", &K) == 1) {
int n = 1<<(K-1);
printf("%d %d\n", n, n-1);
node = 0;
dfs(K);
for(i = 1, j = 0; i <= K; i++)
for(; !C[i].empty(); C[i].pop_back())
printf(j++ ? " %d" : "%d", C[i].back());
puts("");
}
return 0;
}