hdu 3722 Card Game (km)

2014-11-23 23:36:43 · 作者: · 浏览: 3
感觉题中这句“Jimmy wants to stick them into several circles, and each card belongs to one circle exactly.”就是吓唬人的,事实上任意两个字符串都能形成环(并不需要一定有公共前缀, 若没有,score为0)。那这样就成了一个裸的KM了。。。
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i
= 0) { if(a[i] != b[j]) break; i++; j--; } return i; } int main() { while(~scanf("%d", &n)) { solver.n = n; FF(i, 1, n+1) scanf("%s", ch[i]); FF(i, 1, n+1) FF(j, 1, n+1) { if(i == j) solver.w[i][j] = 0; else solver.w[i][j] = get(ch[i], ch[j]); } printf("%d\n", solver.km()); } return 0; }