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.
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.
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.
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
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;
}
文章定位：
