HDU2813 One fihgt one 最小权匹配

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2813

　　典型的最小权覆盖，建图的时候用map标记就可以了，G++一般情况是可以900+ms过得，如果代码写得错了点，就会超时，C++叫一般快200ms的样子。比赛的时候，我加了优化，G++交了n次都超时，后来改成C++交就过了，郁闷得死！后来把map标记改为Trie树，结果203ms飘过，直接刷到了statistic的第三，所以说嘛，Trie的效率不是盖的，以后还是得多用Trie树取代map！

　　其实还有很多优化的，比如用hash优化等等，不过这个效率也够了。

　　map+KM:

 1 //STATUS:C++_AC_734MS_672KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL long long
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int MAX=210,INF=0x7fffffff;
21 
22 map<string,int> ma1,ma2;
23 int w[MAX][MAX],lx[MAX],ly[MAX],S[MAX],T[MAX],y[MAX],g[MAX][MAX];
24 int n,m,k,slack;
25 
26 int dfs(int u)
27 {
28     S[u]=1;
29     int v,t;
30     for(v=1;v<=m;v++){
31         if(g[u][v]){
32             t=w[u][v]-lx[u]-ly[v];
33             if(!t){
34                 if(!T[v]){
35                     T[v]=1;
36                     if(!y[v] || dfs(y[v])){
37                         y[v]=u;
38                         return 1;
39                     }
40                 }
41             }
42             else if(t<slack)slack=t;
43         }
44     }
45     return 0;
46 }
47 
48 int KM()
49 {
50     int i,j,s;
51     mem(y,0);
52     mem(ly,0);
53     for(i=1;i<=n;i++){
54         lx[i]=INF;
55         for(j=1;j<=m;j++)
56             if(g[i][j] && w[i][j]<lx[i])lx[i]=w[i][j];
57     }
58     for(i=1;i<=n;i++){
59         while(1){
60             slack=INF;
61             mem(S,0);mem(T,0);
62             if(dfs(i))break;
63             for(j=1;j<=n;j++)if(S[j])lx[j]+=slack;
64             for(j=1;j<=m;j++)if(T[j])ly[j]-=slack;
65         }
66     }
67     for(s=0,i=1;i<=m;i++)
68         if(y[i])s+=w[y[i]][i];
69     return s;
70 }
71 
72 int main()
73 {
74  //   freopen("in.txt","r",stdin);
75     int i,j,t,cou1,cou2,a,b;
76     char s1[22],s2[22];
77     while(~scanf("%d%d%d",&n,&m,&k))
78     {
79         cou1=cou2=1;
80         mem(g,0);
81         ma1.clear(),ma2.clear();
82         for(i=0;i<k;i++){
83             scanf("%s%s%d",s1,s2,&t);
84             if(!ma1[s1])a=ma1[s1]=cou1++;
85             else a=ma1[s1];
86             if(!ma2[s2])b=ma2[s2]=cou2++;
87             else b=ma2[s2];
88             w[a][b]=t;
89             g[a][b]=1;
90         }
91 
92         printf("%d\n",KM());
93     }
94     return 0;
95 }

　　Trie树+KM：

  1 //STATUS:G++_AC_208MS_18256KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL long long
 15 #define Max(a,b) ((a)>(b)?(a):(b))
 16 #define Min(a,b) ((a)<(b)?(a):(b))
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define lson l,mid,rt<<1
 19 #define rson mid+1,r,rt<<1|1
 20 const int MAX=210,INF=0x7fffffff;
 21 
 22 int w[MAX][MAX],lx[MAX],ly[MAX],S[MAX],T[MAX],y[MAX],g[MAX][MAX];
 23 int n,m,k,slack,cou1,cou2;
 24 struct Trie{
 25     Trie(){mem(p,0);val=-1;}
 26     Trie* p[55];
 27     int val;
 28 };
 29 
 30 int find(char *s,Trie *t,int& cou){
 31     int a;
 32     if(*s<='Z')a=*s-'A';
 33     else a=*s-'a'+26;
 34     if(*(s+1)=='\0'){
 35         if(!t->p[a]){
 36             t->p[a]=new Trie;
 37             return t->p[a]->val=cou++;
 38         }
 39         return t->p[a]->val;
 40     }
 41     if(!t->p[a]){
 42         t->p[a]=new Trie;
 43         return find(s+1,t->p[a],cou);
 44     }
 45     return find(s+1,t->p[a],cou);
 46 }
 47 
 48 int dfs(int u)
 49 {
 50     S[u]=1;
 51     int v,t;
 52     for(v=1;v<=m;v++){
 53         if(g[u][v]){
 54             t=w[u][v]-lx[u]-ly[v];
 55             if(!t){
 56                 if(!T[v]){
 57                     T[v]=1;
 58                     if(!y[v] || dfs(y[v])){
 59                         y[v]=u;
 60                         return 1;
 61                     }
 62                 }
 63             }
 64             else if(t<slack)slack=t;
 65         }
 66     }
 67     return 0;
 68 }
 69 
 70 int KM()
 71 {
 72     int i,j,s;
 73     mem(y,0);
 74     mem(ly,0);
 75     for(i=1;i<=n;i++){
 76         lx[i]=INF;
 77         for(j=1;j<=m;j++)
 78             if(g[i][j] && w[i][j]<lx[i])lx[i]=w[i][j];
 79     }
 80     for(i=1;i<=n;i++){
 81         while(1){
 82             slack=INF;
 83             mem(S,0);mem(T,0);
 84             if(dfs(i))break;
 85             for(j=1;j<=n;j++)if(S[j])lx[j]+=slack;
 86             for(j=1;j<=m;j++)if(T[j])ly[j]-=slack;
 87         }
 88     }
 89     for(s=0,i=1;i<=m;i++)
 90         if(y[i])s+=w[y[i]][i];
 91     return s;
 92 }
 93 int main()
 94 {
 95   //  freopen("in.txt","r",stdin);
 96     int i,j,t,a,b;
 97     char s1[22],s2[22];
 98     while(~scanf("%d%d%d",&n,&m,&k))
 99     {
100         Trie *Node=new Trie;
101         cou1=cou2=1;
102         mem(g,0);
103         for(i=0;i<k;i++){
104             scanf("%s%s%d",s1,s2,&t);
105             a=find(s1,Node,cou1);
106             b=find(s2,Node,cou2);
107             w[a][b]=t;
108             g[a][b]=1;
109         }
110 
111         printf("%d\n",KM());
112     }
113     return 0;
114 }