【HDU 2853】 KM算法

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

题意：有n个公司，m个任务，每个公司做每个任务都有一个效率值，最开始每个公司都指派了一个任务，现在要你重新给每个公司分配一个任务（一个任务只能分配给一家公司），使得所有公司任务的效率值最大，并且改变的原始任务最少。

思路：把每条边的权值扩大k倍（k>n），然后属于原始任务的边权值+1，权值加1是为了当两条边权值相同时，更优先选择属于原始任务的边，扩大k倍的巧妙之处不仅在于KM匹配时优先选择原始边所得答案除k得到原始答案，而且结果对k求余就是保留的就是原始任务的数量。

这种题对思维要求太高了，想不到 T.T

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn=505;
 8 const int oo=1e9;
 9 int lx[maxn], ly[maxn], vx[maxn], vy[maxn], match[maxn], slack[maxn];
10 int map[maxn][maxn];
11 int n, m;
12 
13 bool find(int i)
14 {
15     vx[i]=1;                      ///相等子图中X集合
16     for(int j=1; j<=m; j++)
17         if(!vy[j])
18         {
19             int t=lx[i]+ly[j]-map[i][j];
20             if(t==0)       ///当这条边在相等子图中
21             {
22                 vy[j]=1;                  ///相等子图中Y集合
23                 if(match[j]==-1||find(match[j]))
24                 {
25                     match[j]=i;
26                     return true;
27                 }
28             }
29             else slack[j]=min(slack[j],t);
30         }
31     return false;
32 }
33 
34 int KM()
35 {
36     int  ans=0;
37     memset(match,-1,sizeof(match));
38     memset(ly,0,sizeof(ly));
39     for(int i=1; i<=n; i++)
40     {
41         lx[i]=-oo;
42         for(int j=1; j<=m; j++)
43             lx[i]=max(lx[i],map[i][j]);    ///顶标lx初始化保存的是连接i节点的最大边权值
44     }
45     for(int i=1; i<=n; i++)
46     {
47         for(int j=1; j<=m; j++) slack[j]=oo;
48         while(1)
49         {
50             memset(vx,0,sizeof(vx));
51             memset(vy,0,sizeof(vy));
52             if(find(i)) break;
53             int d=oo;
54             for(int j=1; j<=m; j++)
55                 if(!vy[j]) d=min(d,slack[j]);
56             for(int j=1; j<=n; j++)
57                 if(vx[j]) lx[j]-=d;
58             for(int j=1; j<=m; j++)
59                 if(vy[j]) ly[j]+=d;
60             for(int j=1; j<=m; j++) slack[j]-=d;
61         }
62     }
63     for(int i=1; i<=m; i++)
64         if(match[i]!=-1) ans+=map[ match[i] ][i];
65     return ans;
66 }
67 
68 int main()
69 {
70     while(cin >> n >> m)
71     {
72         for(int i=0; i<=n; i++)
73             for(int j=0; j<=m; j++) map[i][j]=-oo;
74         for(int i=1; i<=n; i++)
75             for(int j=1; j<=m; j++)
76             {
77                  int c;
78                  scanf("%d",&c);
79                  map[i][j]=max(map[i][j],100*c);
80             }
81         int sum=0;
82         for(int i=1,j; i<=n; i++)
83         {
84             scanf("%d",&j);
85             sum+=map[i][j]/100;
86             map[i][j]+=1;
87         }
88         int ans=KM();
89         printf("%d %d
",n-ans%100,ans/100-sum);
90     }
91     return 0;
92 }

View Code