hdu 2255+hdu 3395

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

一直都想把这题切了，可无奈实力还是不够啊！！！看了好久的KM算法，今天总算是有点眉目了，然后就一气呵成把这题切了。。。

以下是KM模版：

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int N=307;
 4 const int inf=10000000;
 5 using namespace std;
 6 int n;
 7 int map[N][N];
 8 bool visitx[N],visity[N];
 9 int lx[N],ly[N];
10 int match[N];
11 
12 //匈牙利算法
13 int Hungary(int u){
14     visitx[u]=true;
15     for(int i=0;i<n;i++){
16         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
17             visity[i]=true;
18             if(match[i]==-1||Hungary(match[i])){
19                 match[i]=u;
20                 return true;
21             }
22         }
23     }
24     return false;
25 }
26 
27 
28 void KM_prefect_match(){
29     int tmp;
30     memset(lx,0,sizeof(lx));//初始化顶标
31     memset(ly,0,sizeof(ly));//ly[i]为0
32     //lx[i]为权值最大边
33     for(int i=0;i<n;i++){
34         for(int j=0;j<n;j++){
35             lx[i]=max(lx[i],map[i][j]);
36         }
37     }
38     for(int i=0;i<n;i++)
39     {
40         while(1){
41             memset(visitx,false,sizeof(visitx));
42             memset(visity,false,sizeof(visity));
43             if(Hungary(i))//匹配成功
44                 break;
45             else {         //匹配失败，找最小值
46                 tmp=inf;
47                 for(int j=0;j<n;j++)if(visitx[j]){   //x在交错树中
48                     for(int k=0;k<n;k++){    //y在交错树外
49                         if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
50                             tmp=lx[j]+ly[k]-map[j][k];
51                         }
52                     }
53                 }
54                 //更新顶标
55                 for(int j=0;j<n;j++){           
56                     if(visitx[j])
57                         lx[j]-=tmp;
58                     if(visity[j])
59                         ly[j]+=tmp;
60                 }
61             }
62         }
63     }
64 }
65 
66 
67 int main(){
68     while(~scanf("%d",&n)){
69         int ans=0;
70         memset(match,-1,sizeof(match));
71         for(int i=0;i<n;i++){
72             for(int j=0;j<n;j++){
73                 scanf("%d",&map[i][j]);
74             }
75         }
76         KM_prefect_match();
77         for(int i=0;i<n;i++){
78             ans+=map[match[i]][i];
79         }
80         printf("%d\n",ans);
81     }
82     return 0;
83 }

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

View Code

 1 #include<iostream>
 2 const int N=110;
 3 const int inf=100000000;
 4 using namespace std;
 5 int n;
 6 int value[N];
 7 int map[N][N];
 8 int lx[N],ly[N];
 9 bool visitx[N],visity[N];
10 int match[N];
11 
12 //匈牙利算法
13 int Hungary(int u){
14     visitx[u]=true;
15     for(int i=0;i<n;i++){
16         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
17             visity[i]=true;
18             if(match[i]==-1||Hungary(match[i])){
19                 match[i]=u;
20                 return 1;
21             }
22         }
23     }
24     return 0;
25 }
26 
27 
28 void KM_prefect_match(){
29     int tmp;
30     memset(lx,0,sizeof(lx));//初始化顶标
31     memset(ly,0,sizeof(ly));//lx[i]为0
32     for(int i=0;i<n;i++){  //lx[i]为权值最大的边
33         for(int j=0;j<n;j++){
34             lx[i]=max(lx[i],map[i][j]);
35         }
36     }
37     //对n个点进行匹配
38     for(int i=0;i<n;i++){
39         while(1){
40             memset(visitx,false,sizeof(visitx));
41             memset(visity,false,sizeof(visity));
42             if(Hungary(i))//匹配成功
43                 break;
44             else {  //匹配失败，找最小值
45                 tmp=inf;
46                 for(int j=0;j<n;j++){  //x在交错树中
47                     if(visitx[j]){
48                         for(int k=0;k<n;k++){    //y在交错树外
49                             if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
50                                 tmp=lx[j]+ly[k]-map[j][k];
51                             }
52                         }
53                     }
54                 }
55                 //更新顶标
56                 for(int j=0;j<n;j++){
57                     if(visitx[j])
58                         lx[j]-=tmp;
59                     if(visity[j])
60                         ly[j]+=tmp;
61                 }
62             }
63         }
64     }
65 }
66 
67 int main(){
68     while(~scanf("%d",&n)&&n){
69         char str[N];
70         for(int i=0;i<n;i++){
71             scanf("%d",&value[i]);
72         }
73         for(int i=0;i<n;i++){
74             scanf("%s",str);
75             for(int j=0;j<n;j++){
76                 map[i][j]=str[j]-'0';
77                 if(map[i][j]){
78                     map[i][j]=(value[i]^value[j]);
79                 }
80             }
81         }
82         int ans=0;
83         memset(match,-1,sizeof(match));
84         KM_prefect_match();
85         for(int i=0;i<n;i++){
86             ans+=map[match[i]][i];
87         }
88         printf("%d\n",ans);
89     }
90     return 0;
91 }