哈理工oj 1392Leyni, LOLI and Houses解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1392

二分匹配的多重匹配再加上二分枚举，本来以为用km算法呢，但是想了下要找的是边的最大值，看来是不可行。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define N 210
 5 #define M 35
 6 #define C 20
 7 #define inf 0xfffffff
 8 using namespace std;
 9 int a[N+M][N+M];//原始存储的距离矩阵
10 int map[N][M*C];//转化为二分图后的距离矩阵
11 int match[M*C];
12 bool usedy[M*C];
13 int n,m,c;
14 bool dfs(int x,int l)//对匈牙利算法的搜索函数进行了一下更改
15 {
16     int i,j,k;
17     for(i=1;i<=m*c;i++)
18     {
19         if(map[x][i]>l)
20         continue;
21         if(!usedy[i])
22         {
23             usedy[i]=true;
24             if(match[i]==-1||dfs(match[i],l))
25             {
26                 match[i]=x;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 int main()
34 {
35     int i,j,k;
36     int d;
37     int t;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%d%d%d",&m,&n,&c);
42         for(i=1;i<=m+n;i++)
43         for(j=1;j<=m+n;j++)
44         {
45             scanf("%d",&d);
46             if(i!=j&&d==0)
47             a[i][j]=inf;
48             else
49             a[i][j]=d;
50         }
51         int low=inf;
52         int high=0;
53         for(k=1;k<=n+m;k++)
54         for(i=1;i<=m+n;i++)
55         for(j=1;j<=n+m;j++)
56         {
57             if(a[i][j]>a[i][k]+a[k][j])
58             a[i][j]=a[i][k]+a[k][j];
59         }
60         for(i=1;i<=m+n;i++)
61         for(j=1;j<=n+m;j++)
62         {
63             if(a[i][j]<low)
64             low=a[i][j];
65             if(a[i][j]>high)
66             high=a[i][j];
67         }
68         for(i=1;i<=n;i++)
69         for(j=0;j<c;j++)
70         for(k=1;k<=m;k++)
71         map[i][j*m+k]=a[m+i][k];
72         int mid;
73         int ans;
74         while(low<=high)//二分枚举
75         {
76             memset(match,-1,sizeof(match));
77             mid=(low+high)>>1;
78             for(i=1;i<=n;i++)
79             {
80                 memset(usedy,0,sizeof(usedy));
81                 if(!dfs(i,mid))
82                 break;
83             }
84             if(i>n)
85             {
86                 high=mid-1;
87                 ans=mid;
88             }
89             else
90             low=mid+1;
91         }
92         printf("%d\n",ans);
93     }
94     return 0;
95 }