hdu 3722 Card Game km

把i 和 j写错了找得人都要抓狂了。。

题意：

给出n个字符串,其中任意两个字符串(包括同一字符串)可以进行互相拼接起来,例如s1="abcd"……>s2="dcab",表示将s1拼接在s2后面,所得的值就是将s1反转得"dcba",该字符串与s2同有的前缀为"dc",所以值就是2.现在求解在n个字符串给定的情况下,将这些字符串拼接起来所得到的最大值.

关键是建图，之后运用KM算法，ok！

  1 #include<iostream>
  2 #include<string.h>
  3 #include<stdio.h>
  4 int mark[1002],n;
  5 char ss[202][1020];
  6 int g[202][202],s[202],t[202],lx[202],ly[202],link[202],d[202];
  7 char temp[1002];
  8 
  9 int max(int x,int y)
 10 {
 11     return x<y?y:x;
 12 }
 13 
 14 int min(int x,int y)
 15 {
 16     return x<y?x:y;
 17 }
 18 
 19 void rev(int x,int len)
 20 {
 21     int i,j;
 22     for(i=0,j=len-1;i<len;i++,j--)
 23         temp[j]=ss[x][i];
 24 }
 25 
 26 void build()
 27 {
 28     int i,j,len,k,count;
 29     for(i=0;i<n;i++)
 30         for(j=0;j<n;j++)
 31         {
 32             if(i==j)
 33             {
 34                 g[i][j]=0;
 35                 continue ;
 36             }
 37             len=strlen(ss[i]);
 38             rev(i,len);
 39             count=0; int len2=strlen(ss[j]);
 40             for(k=0;temp[k]==ss[j][k]&&k<len&&k<len2;k++)
 41                 count++;
 42             g[i][j]=count;
 43         }
 44 }
 45 
 46 int dfs(int x)
 47 {
 48     s[x]=1;
 49     for(int i=0;i<n;i++)
 50     {
 51         
 52         if(t[i]==1)
 53             continue;int temp=lx[x]+ly[i]-g[x][i];
 54         if(temp==0)
 55         {
 56             t[i]=1;
 57             if(link[i]==-1||dfs(link[i]))
 58             {
 59                 link[i]=x;
 60                 return 1;
 61             }
 62         }
 63         else d[i]=temp<d[i]?temp:d[i];
 64     }
 65     return 0;
 66 }
 67 
 68 void update()
 69 {
 70     int i,j;
 71     int a=1<<30;
 72 //    for(i=0;i<n;i++)
 73     //    if(s[i])
 74             for(j=0;j<n;j++)
 75                 if(!t[j])
 76                     a=min(a,d[j]);
 77    for(i=0;i<n;i++)
 78    {
 79        if(s[i]) lx[i]-=a;
 80        if(t[i]) ly[i]+=a;
 81    }
 82 }
 83 
 84 
 85 
 86 void KM()
 87 {
 88     int i,j;
 89     for(i=0;i<n;i++)
 90     {
 91         lx[i]=ly[i]=g[i][0];
 92         for(j=0;j<n;j++)
 93             lx[i]=max(lx[i],g[i][j]);
 94     }
 95     memset(link,-1,sizeof(link));
 96     for(i=0;i<n;i++)
 97     {
 98         for(j=0;j<n;j++)
 99             d[j]=1<<30;
100         while(1)
101         {
102             memset(s,0,sizeof(s));
103             memset(t,0,sizeof(t));
104             if(dfs(i))
105                 break;
106             else update();
107         }
108     }
109 }
110 
111 
112 int main()
113 {
114     int i,j;
115     while(scanf("%d",&n)!=EOF)
116     {
117         for(i=0;i<n;i++)
118             scanf("%s",ss[i]);
119         build();
120         KM();
121         for(i=0;i<n;i++)
122             dfs(i);
123         int ans=0;
124         for(i=0;i<n;i++)
125             ans+=g[link[i]][i];
126         
127         printf("%d
",ans);
128     }
129     return 0;
130 }