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.
1 ≤ N ≤ 30,
1 ≤ n ≤ 26,
1 ≤ ki ≤ 26.
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