hdu 3488+hdu 3435(多个环的并）

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

思路：KM算法求最小权。。。

ps:任何完全图的二分匹配其实就是n个环的并

View Code

 1 #include<iostream>
 2 const int MAXN=222;
 3 const int inf=1<<30;
 4 using namespace std;
 5 int n,m;
 6 int map[MAXN][MAXN];
 7 int lx[MAXN],ly[MAXN];
 8 int match[MAXN];
 9 bool visitx[MAXN],visity[MAXN];
10 
11 int Hungary(int u){
12     visitx[u]=true;
13     for(int i=1;i<=n;i++){
14         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
15             visity[i]=true;
16             if(match[i]==-1||Hungary(match[i])){
17                 match[i]=u;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 
25 
26 void KM_prefect_match(){
27     int tmp;
28     for(int i=1;i<=n;i++){
29         lx[i]=-inf;                     //初始化应该赋为无穷小
30     }
31     memset(ly,0,sizeof(ly));
32     for(int i=1;i<=n;i++){
33         for(int j=1;j<=n;j++){
34             lx[i]=max(lx[i],map[i][j]);    
35         }
36     }
37     for(int i=1;i<=n;i++)
38     {
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=1;j<=n;j++)if(visitx[j]){   //x在交错树中
47                     for(int k=1;k<=n;k++){
48                         if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
49                             tmp=lx[j]+ly[k]-map[j][k];
50                         }
51                     }
52                 }
53                 for(int j=1;j<=n;j++){
54                     if(visitx[j])
55                         lx[j]-=tmp;
56                     if(visity[j])
57                         ly[j]+=tmp;
58                 }
59             }
60         }
61     }
62 }
63 
64 
65 int main(){
66     int _case;
67     scanf("%d",&_case);
68     while(_case--){
69         scanf("%d%d",&n,&m);
70         memset(match,-1,sizeof(match));
71         for(int i=1;i<=n;i++){
72             for(int j=1;j<=n;j++){
73                 map[i][j]=-inf;
74             }
75         }
76         for(int i=1;i<=m;i++){
77             int x,y,w;
78             scanf("%d%d%d",&x,&y,&w);
79             if(map[x][y]<-w){
80                 map[x][y]=-w;
81             }
82         }
83         KM_prefect_match();
84         int ans=0;
85         for(int i=1;i<=n;i++){
86             ans+=map[match[i]][i];
87         }
88         printf("%d\n",-ans);
89     }
90     return 0;
91 }

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

View Code

 1 #include<iostream>
 2 const int MAXN=1010;
 3 const int inf=1<<30;
 4 using namespace std;
 5 int n,m;
 6 int map[MAXN][MAXN];
 7 int match[MAXN];
 8 int lx[MAXN],ly[MAXN];
 9 bool visitx[MAXN],visity[MAXN];
10 
11 int Hungary(int u){
12     visitx[u]=true;
13     for(int i=1;i<=n;i++){
14         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
15             visity[i]=true;
16             if(match[i]==-1||Hungary(match[i])){
17                 match[i]=u;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 
25 
26 void KM_prefect_match(){
27     int tmp;
28     for(int i=1;i<=n;i++){
29         lx[i]=-inf;
30     }
31     memset(ly,0,sizeof(ly));
32     for(int i=1;i<=n;i++){
33         for(int j=1;j<=n;j++){
34             lx[i]=max(lx[i],map[i][j]);
35         }
36     }
37     for(int i=1;i<=n;i++)
38     {
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=1;j<=n;j++)if(visitx[j]){
47                     for(int k=1;k<=n;k++){
48                         if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
49                             tmp=lx[j]+ly[k]-map[j][k];
50                         }
51                     }
52                 }
53                 for(int j=1;j<=n;j++){
54                     if(visitx[j])
55                         lx[j]-=tmp;
56                     if(visity[j])
57                         ly[j]+=tmp;
58                 }
59             }
60         }
61     }
62 }
63 
64 int main(){
65     int T,_case=1;
66     scanf("%d",&T);
67     while(T--){
68         scanf("%d%d",&n,&m);
69         memset(match,-1,sizeof(match));
70         for(int i=1;i<=n;i++){
71             for(int j=1;j<=n;j++){
72                 map[i][j]=-inf;
73             }
74         }
75         for(int i=1;i<=m;i++){
76             int x,y,w;
77             scanf("%d%d%d",&x,&y,&w);
78             if(map[x][y]<-w){
79                 map[x][y]=map[y][x]=-w;
80             }
81         }
82         KM_prefect_match();
83         printf("Case %d: ",_case++);
84         int ans=0;
85         int flag=false;
86         for(int i=1;i<=n;i++){
87             if(match[i]==-1||map[match[i]][i]==-inf){
88                 flag=true;
89                 break;
90             }
91             ans+=map[match[i]][i];
92         }
93         if(flag){
94             printf("NO\n");
95         }else 
96             printf("%d\n",-ans);
97     }
98     return 0;
99 }