首页 > 其他 > 详细

UVa11418 - Clever Naming Patterns

时间:2014-04-12 12:06:23      阅读:487      评论:0      收藏:0      [点我收藏+]

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, NN 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 ki - 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 ≤ ki ≤ 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

1 Ad

Case #1:
Apples
Bananas
Cranberries
Case #2:
Apples
Case #3:
Axe
B
Case #4:
Ad
Bc
Cb

Da


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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!