POJ 1795

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define maxn 105
  8 
  9 #define INF 10000
 10 
 11 int n,ca,len,sum;
 12 char s[20][maxn];
 13 int dp[20][(1 << 15) + 5],dis[20][20];
 14 bool vis[20],done[20];
 15 string ans;
 16 
 17 int cal(int x,int y) {
 18         int  _max = 0;
 19         for(int i = 0; i < strlen(s[x]); i++) {
 20                 if(s[x][i] != s[y][0]) continue;
 21                 int j,k;
 22                 for( j = i,k = 0; j < strlen(s[x]) && k < strlen(s[y]); j++,k++) {
 23                         if(s[x][j] != s[y][k]) break;
 24                 }
 25                 if(k == strlen(s[y])) {
 26                         done[y] = 1;
 27                         break;
 28                 }
 29                 if(j == strlen(s[x])) {
 30                         _max = max(_max,j - i);
 31 
 32                 }
 33         }
 34 
 35 
 36         return -_max;
 37 }
 38 void init() {
 39     for(int u = 0; u < n; u++) {
 40             if(done[u]) continue;
 41             for(int v = 0; v < n; v++) {
 42                     if(u == v || done[v]) continue;
 43                     dis[u][v] = cal(u,v);
 44 
 45 
 46             }
 47     }
 48 
 49 
 50 }
 51 
 52 void dfs(int v,int s1) {
 53         vis[v] = 1;
 54         int id = -1;
 55         string t("z");
 56         for(int u = 0; u < n; u++) {
 57                 if(done[u] || vis[u]) continue;
 58 
 59                 if(dp[v][s1] == dp[u][s1 | (1 << u)] + dis[v][u]) {
 60                         string t1(s[u] - dis[v][u],s[u] + strlen(s[u]));
 61                         if(t > t1) {
 62                                 t = t1;
 63                                 id = u;
 64                         }
 65                 }
 66 
 67 
 68         }
 69 
 70         if(id != -1) {
 71                 ans = ans + t;
 72                 dfs(id,s1 | (1 << id));
 73 
 74         }
 75 }
 76 
 77 
 78 
 79 
 80 
 81 void solve() {
 82     init();
 83 
 84     for(int s1 = (1 << n) - 2; s1; s1--) {
 85             for(int v = 0; v < n; v++) {
 86                     if(!(s1 & (1 << v)) || done[v]) continue;
 87                     for(int u = 0; u < n; u++) {
 88                             if(u == v || (s1 & (1 << u)) || done[v] ) continue;
 89                             dp[v][s1] = min(dp[v][s1],dp[u][s1 | (1 << u)] + dis[v][u]);
 90 
 91                     }
 92             }
 93     }
 94 
 95     int _min = 0;
 96     for(int i = 0; i < n; i++) {
 97             if(done[i]) continue;
 98             _min = min(_min,dp[i][1 << i]);
 99     }
100 
101     memset(vis,0,sizeof(vis));
102 
103     ans = "z";
104     int id;
105     for(int i = 0; i < n; i++) {
106             if(done[i]) continue;
107             string t(s[i]);
108             if(dp[i][1 << i] == _min && ans > t) {
109                     ans = t;
110                     id = i;
111             }
112     }
113 
114     dfs(id,1 << id);
115 
116     printf("Scenario #%d:\n",ca++);
117     cout << ans << endl;
118 
119 
120 
121 }
122 int main()
123 {
124     int t;
125     //freopen("sw.in","r",stdin);
126     scanf("%d",&t);
127     ca = 1;
128 
129     while(t--) {
130             memset(done,0,sizeof(done));
131 
132             scanf("%d",&n);
133 
134             for(int i = 0; i < n; i++) {
135                     scanf("%s",s[i]);
136             }
137 
138             memset(dis,0,sizeof(dis));
139 
140             for(int i = 0; i < n; i++) {
141                     for(int s = 0; s < (1 << n); s++) {
142                             dp[i][s] = 0;
143                     }
144             }
145 
146             solve();
147             printf("\n");
148 
149     }
150 
151     return 0;
152 }