紫书搜索 例题7-6 UVA - 140 Bandwidth

题目链接:

https://vjudge.net/problem/UVA-140

题意:

题解:

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; char s[500]; int mp[30][30],vis[30],save[100],node[100]; int main(){ while(gets(s)){ if(!strcmp(s,"#")) break; int ans = 10; int len = strlen(s); MS(vis); MS(mp); int u, flag = 0; for(int i=0; i<len; i++){ if(s[i]>='A' && s[i]<='Z') vis[s[i]-'A'] = 1; if(s[i] == ':'){ u = s[i-1]-'A'; flag = 1; }else if(flag && s[i]!=';'){ mp[u][s[i]-'A'] = mp[s[i]-'A'][u] = 1; }else{ flag = 0; } } int cnt = 0; for(int i=0; i<26; i++) if(vis[i]) node[cnt++] = i; do{ int num = 0; for(int i=0; i<cnt; i++){ for(int j=i+1; j<cnt; j++){ if(mp[node[i]][node[j]]) if(j-i > num) num = j-i; } if(num >= ans) break; } if(ans > num){ ans = num; memcpy(save,node,sizeof(node)); } }while(next_permutation(node,node+cnt)); for(int i=0; i<cnt; i++){ printf("%c ",save[i]+'A'); } printf("-> %d\n",ans); } return 0; }