[UVA][組合] 10475 - Help the Leaders
Help the Leaders
| Help the Leaders |
Have you ever listened to the speeches of leaders (Political or non-political)? People often find these speeches monotonous and hopeless. The leaders also sometimes feel very embarrassed about their speeches and they are often afraid of covering the same topics in two different speeches. You can save our intelligent leaders from these kinds of embarrassments. For example, let's consider that a leader has the following topics in his mind
- a)
- War
- b)
- Terror
- c)
- Peace
- d)
- Nuclear-Bomb
- e)
- Human-Right
- f)
- Food
- g)
- Oil-Crisis
- h)
- Equal-Right
He delivers speeches on any two of these topics at once but never wants to cover the topics ``Oil- Crisis" and ``War" in the same speech. The same thing applies for the topics ``Nuclear-Bomb" and ``Equal-Right". You can help him by making all possible combinations of topics (Of course considering the restrictions supplied by him) so that he can choose any one from them according to his convenience and can avoid any blunders. The specific details are given in the input and output specifications.
Input
The first line of the input file contains an integer n(n
100), which indicates how
many sets of inputs are there. The description of each set is given in the paragraph below:
The first line of each set has three integers t(
0 < t < 16), p(
0p < t(t - 1)/2),
s(
0 < s5). Here t denotes the number of topics in the leader's mind, p denotes
the number of prohibited pairs and s is the
total number of topics the leader wants to cover in a single speech. The next t lines contain t
topics of the leader's mind. The topics are all different. Each topic will contain only
alphanumeric characters and hyphens. Each of the next p lines contains two different topics in
each line separated by a single space. These pairs of topics should not come in the same speech.
Same pair of topics may appear more than once in the input. Each topic has a maximum length
of 15.
Output
For each set you should first print the serial of that set. Each of the next lines should contain all the possible topic groups. The topics in each group should be separated by a single space. Print a blank line after the output for each set of input. In a group the topics should be printed in the descending order of their lengths. If lengths of two topics are same the lexicographically smaller one should come first. This order should also be maintained in the printing order of the groups.
Topics should be considered case insensitive. While printing the topics print all the characters as uppercase. Print a blank line after the output for each case.
Sample Input
2 8 2 2 WAR TERROR PEACE NUCLEAR-BOMB HUMAN-RIGHT FOOD OIL-CRISIS EQUAL-RIGHT WAR OIL-CRISIS EQUAL-RIGHT NUCLEAR-BOMB 8 0 1 WAR TERROR PEACE NUCLEAR-BOMB HUMAN-RIGHT FOOD OIL-CRISIS EQUAL-RIGHT
Output for Sample Input
Set 1: NUCLEAR-BOMB HUMAN-RIGHT NUCLEAR-BOMB OIL-CRISIS NUCLEAR-BOMB TERROR NUCLEAR-BOMB PEACE NUCLEAR-BOMB FOOD NUCLEAR-BOMB WAR EQUAL-RIGHT HUMAN-RIGHT EQUAL-RIGHT OIL-CRISIS EQUAL-RIGHT TERROR EQUAL-RIGHT PEACE EQUAL-RIGHT FOOD EQUAL-RIGHT WAR HUMAN-RIGHT OIL-CRISIS HUMAN-RIGHT TERROR HUMAN-RIGHT PEACE HUMAN-RIGHT FOOD HUMAN-RIGHT WAR OIL-CRISIS TERROR OIL-CRISIS PEACE OIL-CRISIS FOOD TERROR PEACE TERROR FOOD TERROR WAR PEACE FOOD PEACE WAR FOOD WAR Set 2: NUCLEAR-BOMB EQUAL-RIGHT HUMAN-RIGHT OIL-CRISIS TERROR PEACE FOOD WAR
Problem-setter: Shahriar Manzoor, ACM Valladolid Online Judge
題目給定演講標題，有些標題不會同時講，而每次要演講的題目指定個數，
生成所有可能的組合方式。必須按照字典順序輸出，在窮舉前先進行排序。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n, cond, m, g[20][20];
string topic[20];
int ch[20];
void dfs(int idx, int i) {
if(idx == m) {
for(i = 0; i < idx; i++) {
if(i) putchar(' ');
printf("%s", topic[ch[i]].c_str());
}
puts("");
return ;
}
int j;
for(; i < n; i++) {
for(j = 0; j < idx; j++)
if(g[i][ch[j]] == 1)
break;
if(j == idx) {
ch[idx] = i;
dfs(idx+1, i+1);
}
}
}
bool cmp(string a, string b) {
if(a.length() != b.length())
return a.length() > b.length();
return a < b;
}
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &n, &cond, &m);
memset(g, 0, sizeof(g));
int i, j, k;
for(i = 0; i < n; i++) {
cin >> topic[i];
for(j = 0; j < topic[i].length(); j++) {
if(topic[i][j] >= 'a' && topic[i][j] <= 'z')
topic[i][j] -= 32;
}
}
sort(topic, topic+n, cmp);
map<string, int> R;
for(i = 0; i < n; i++)
R[topic[i]] = i;
while(cond--) {
string tx, ty;
cin >> tx >> ty;
for(i = 0; i < tx.length(); i++) {
if(tx[i] >= 'a' && tx[i] <= 'z')
tx[i] -= 32;
}
for(i = 0; i < ty.length(); i++) {
if(ty[i] >= 'a' && ty[i] <= 'z')
ty[i] -= 32;
}
int x = R[tx], y = R[ty];
g[x][y] = g[y][x] = 1;
}
printf("Set %d:\n", ++cases);
dfs(0, 0);
puts("");
}
return 0;
}