题目链接:
https://vjudge.net/problem/UVA-140
题意:
题解:
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 char s[500]; 19 int mp[30][30],vis[30],save[100],node[100]; 20 21 int main(){ 22 while(gets(s)){ 23 if(!strcmp(s,"#")) break; 24 int ans = 10; 25 int len = strlen(s); 26 MS(vis); MS(mp); 27 int u, flag = 0; 28 for(int i=0; i<len; i++){ 29 if(s[i]>='A' && s[i]<='Z') 30 vis[s[i]-'A'] = 1; 31 if(s[i] == ':'){ 32 u = s[i-1]-'A'; 33 flag = 1; 34 }else if(flag && s[i]!=';'){ 35 mp[u][s[i]-'A'] = mp[s[i]-'A'][u] = 1; 36 }else{ 37 flag = 0; 38 } 39 } 40 int cnt = 0; 41 for(int i=0; i<26; i++) 42 if(vis[i]) 43 node[cnt++] = i; 44 45 do{ 46 int num = 0; 47 for(int i=0; i<cnt; i++){ 48 for(int j=i+1; j<cnt; j++){ 49 if(mp[node[i]][node[j]]) 50 if(j-i > num) 51 num = j-i; 52 } 53 if(num >= ans) break; 54 } 55 if(ans > num){ 56 ans = num; 57 memcpy(save,node,sizeof(node)); 58 } 59 }while(next_permutation(node,node+cnt)); 60 61 for(int i=0; i<cnt; i++){ 62 printf("%c ",save[i]+'A'); 63 } 64 printf("-> %d ",ans); 65 66 } 67 68 return 0; 69 }