Problem B
Clever Naming Patterns
Input: Standard Input

Output: Standard Output

Piotr is organizing a programming competition consisting of n problems, numbered A, B, C, etc. He wants to name the first problem starting with the letter A, the second problem starting with the letter B, and so on. However, he cannot simply come up with random words for problem titles - that wouldn‘t make sense. For each problem, he has come up with a list of acceptable names. Help Piotr pick an ordering of the problems and an acceptable name for each one so that each problem‘s name starts with the correct letter of the alphabet.

Input

The first line of input gives the number of cases, N. N test cases follow. Each one starts with n on a line by itself. The next n lines list the possible names for each of the n problems. Each line starts with k_i - the number of acceptable names for problem i and lists the names, separated by spaces. Each name is a non-empty string of letters. No two names will be the same, and no two names for the same problem will start with the same letter.

1 ≤ N ≤ 30,
1 ≤ n ≤ 26,
1 ≤ k_i ≤ 26.

Output

For each test case, first output the line "Case #x:", where x is the test case number. After that, print n lines listing the n problem names, each with only the first letter capitalized. There is guaranteed to be exactly one solution.

Sample Input                                         Output for Sample Input

4

3

2 Apples Oranges

1 Bananas

5 Apricots Blueberries Cranberries Zuccini Yams

1

1 ApPlEs

2

2 a b

1 axe

4

4 Aa Ba Ca Da

3 Ab Bb Cb

2 Ac Bc

Case #1:

Apples

Bananas

Cranberries

Case #2:

Apples

Case #3:

Axe

B

Case #4:

Ad

Bc

Cb

Problem setter: Igor Naverniouk

水果

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 30;
int n,cnt;
int head[maxn],from[maxn];
bool vis[maxn];
vector<string> g[maxn];
struct Edge{
    int nxt,to;
}edge[maxn*maxn];

void addedge(int from,int to){
        ++cnt;
        edge[cnt].nxt = head[from];
        edge[cnt].to = to;
        head[from] = cnt;
}

void init(){
    cnt = 0;
    memset(head,-1,sizeof head);
    memset(from,-1,sizeof from);
    for(int i = 0; i < maxn; i++) g[i].clear();
}

bool dfs(int x){
    for(int i = head[x]; i != -1;i = edge[i].nxt){
        int v = edge[i].to;
        if(!vis[v]){
            vis[v] = 1;
            if(from[v]==-1||dfs(from[v])){
                from[v] = x;
                return 1;
            }
        }
    }
    return 0;
}

void hungary(){
    int ans = 0;
    for(int i = 0; i < n; i++){
        memset(vis,0,sizeof vis);
        if(dfs(i)) ans++;
    }
}

int main(){

    int ncase,T=1;
    cin >> ncase;
    while(ncase--){
        cin >> n;
        init();
        int k;
        string tmp;
        for(int i = 0; i < n; i++){
            cin >> k;
            while(k--){
                cin >> tmp;
                if(tmp[0]>=‘a‘&&tmp[0]<=‘z‘) tmp[0] = tmp[0]-‘a‘+‘A‘;
                if(tmp[0]-‘A‘<n){
                    for(int j = 1; j < tmp.size(); j++){
                        if(tmp[j]>=‘A‘&&tmp[j]<=‘Z‘)
                            tmp[j] = tmp[j]-‘A‘+‘a‘;
                        }
                        g[i].push_back(tmp);
                        addedge(i,tmp[0]-‘A‘);
                }
            }
        }
        printf("Case #%d:\n",T++);
        hungary();
        for(int i = 0; i < n; i++){
            int x = from[i];
            for(int j =0; j < g[x].size(); j++){
                if(g[x][j][0]==char(i+‘A‘)){
                    cout<<g[x][j]<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

UVa11418 - Clever Naming Patterns,布布扣,bubuko.com

UVa11418 - Clever Naming Patterns

原文：http://blog.csdn.net/mowayao/article/details/23436705