Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n个串，a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。
思路：先暴力处理出每两个的权值。。2002001000的复杂度。。还是可以接受的。。
然后把每个串看成了一个点，由于一个串最多可以被放在前面一次，被放在后面一次，所以可以类比图论中的环的入度和出度为1.
然后跑一遍KM. 1A,开心。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年06月02日 星期四 23时37分55秒
4File Name :code/hdu/3722.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=205;
34int n;
35char st[N][1005];
36int w[N][N];
37int link[N];
38int lx[N],ly[N];
39bool visx[N],visy[N];
40int slk[N];
41int solve(string a,string b)
42{
43 int la = a.length();
44 int lb = b.length();
45 int len = min(la,lb);
46 int res = 0 ;
47 for ( int i = 0 ; i < len ; i++)
48 {
49 if (b[i]==a[la-1-i]) res++;
50 else break;
51 }
52 return res;
53}
54
55bool find( int u)
56{
57 // cout<<"u:"<<u<<endl;
58 visx[u] = true;
59 for ( int v = 1 ; v <= n ; v++)
60 {
61 if (visy[v]) continue;
62
63 int tmp = lx[u] + ly[v] - w[u][v];
64 if (tmp==0)
65 {
66 visy[v] = true;
67 if (link[v]==-1||find(link[v]))
68 {
69 link[v] = u ;
70 return true;
71 }
72 }else if (tmp<slk[v]) slk[v] = tmp;
73 }
74 return false;
75}
76int KM()
77{
78 ms(lx,0);
79 ms(ly,0);
80 ms(link,-1);
81
82 for ( int i = 1 ; i <= n ; i++)
83 for ( int j = 1 ; j <= n ; j++ )
84 lx[i] = max(lx[i],w[i][j]);
85
86 for ( int i = 1; i <= n ; i++)
87 {
88 ms(slk,0x3f);
89
90 while (1)
91 {
92 ms(visx,false);
93 ms(visy,false);
94
95 if (find(i)) break;
96
97 int d = inf;
98
99 for ( int j = 1 ; j <= n ; j++)
100 if (!visy[j]&&slk[j]<d) d= slk[j];
101
102 for ( int j = 1 ; j <= n ; j++)
103 if (visx[j]) lx[j]-=d;
104
105 for ( int j = 1 ; j <= n ; j++)
106 if (visy[j]) ly[j]+=d ; else slk[j]-=d;
107 }
108 }
109 int res = 0 ;
110 for ( int i = 1 ; i <= n ; i++)
111 if (link[i]>-1) res += w[link[i]][i];
112
113 return res;
114}
115int main()
116{
117 #ifndef ONLINE_JUDGE
118 freopen("code/in.txt","r",stdin);
119 #endif
120
121 while (~scanf("%d",&n))
122 {
123 for ( int i = 1 ; i <= n ; i++) scanf("%s",st[i]);
124
125 ms(w,0);
126
127 for ( int i = 1 ; i <= n ; i++)
128 for ( int j = 1 ; j <= n ; j++)
129 if (i!=j) w[i][j] = solve(string(st[i]),string(st[j]));
130
131 // for ( int i = 1 ; i <= n ; i++)
132 // for ( int j = 1 ; j <= n ; j++) if (i!=j) cout<<"w[i][j]:"<<w[i][j]<<endl;
133
134 int ans = KM();
135 printf("%d\n",ans);
136 }
137
138 #ifndef ONLINE_JUDGE
139 fclose(stdin);
140 #endif
141 return 0;
142}