hdu2853 Assignment 完美匹配多校联赛的好题

PS:好题。不看题解绝对AC不了。

题解来源：

http://blog.csdn.net/niushuai666/article/details/7176290

http://www.cnblogs.com/wally/archive/2013/04/02/2995846.html

题目大意：

　　现在有N个部队和M个任务（M>=N），每个部队完成每个任务有一点的效率，效率越高越好。但是部队已经安排了一定的计划，这时需要我们尽量用最小的变动，使得所有部队效率之和最大。求最小变动的数目和变动后和变动前效率之差。

分析：

　　因为我们要变动最小，所以对在原计划中的边要有一些特殊照顾，使得最优匹配时，尽量优先使用原计划的边，这样变化才能是最小的且不会影响原匹配。

　　根据这个思想，我们可以把每条边的权值扩大k倍，k要大于n。然后对原计划的边都+1。精华全在这里。我们来详细说明一下。

　　全部边都扩大了k倍，而且k比n大，这样，我们求出的最优匹配就是k倍的最大权值，只要除以k就可以得到最大权值。实现原计划的边加1，这样，在每次选择边时，这些变就有了优势，就会优先选择这些边。假如原计划的h条边被选入了最优匹配中，这样，最优权值就是k倍的最大权值+k（原计划的每条边都+1）。但是k大于n的用意何在呢？我们发现假如原计划的边全部在匹配中，只会增加n，又n<k,所以除以k后不会影响最优匹配的最大权值之和，然后我们对k取余，就正好得到加入的原计划的边的个数。这时，我们只需要用总点数-加入的原计划的点数，就可以求得最小变动数了。

代码：（其实知道上面的题解，根本不用看代码）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=55, INF=0x3f3f3f3f;
 7 int Map[N][N],mat1[N],mat2[N];//匹配上的左右集合
 8 int KM(int m,int n)
 9 {
10     int s[N],t[N],a[N],b[N];
11     int i,j,k,p,q,ans=0;
12     for(i=0;i<m;i++)
13     {
14         a[i]=-INF;
15         for(j=0;j<n;j++)
16             a[i]=Map[i][j]>a[i]?Map[i][j]:a[i];
17         if(a[i]==-INF) return -1;//cannot match
18     }
19     memset(b,0,sizeof(b));
20     memset(mat1,-1,sizeof(mat1));
21     memset(mat2,-1,sizeof(mat2));
22     for(i=0;i<m;i++)
23     {
24         memset(t,-1,sizeof(t));
25         p=q=0;
26         for(s[0]=i;p<=q&&mat1[i]<0;p++)
27         {
28             for(k=s[p],j=0;j<n&&mat1[i]<0;j++)
29             {
30                 if(a[k]+b[j]==Map[k][j]&&t[j]<0)
31                 {
32                     s[++q]=mat2[j]; t[j]=k;
33                     if(s[q]<0)
34                         for(p=j;p>=0;j=p)
35                         {
36                             mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j;
37                         }
38                 }
39             }
40         }
41         if(mat1[i]<0)
42         {
43             i--,p=INF;
44             for(k=0;k<=q;k++)
45             {
46                 for(j=0;j<n;j++)
47                     if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p)
48                         p=a[s[k]]+b[j]-Map[s[k]][j];
49             }
50             for(j=0;j<n;j++) b[j]+=t[j]<0?0:p;
51             for(k=0;k<=q;k++) a[s[k]]-=p;
52         }
53 }
54     for(i=0;i<m;i++) ans+=Map[i][mat1[i]];
55     return ans;
56 }
57 int p[N];
58 int main()
59 {
60     //freopen("test.txt","r",stdin);
61     int n,i,j,m,k,e,t,ans,s;
62     while(scanf("%d%d",&n,&m)!=EOF)
63     {
64         e=n;
65         for(i=0;i<n;i++)
66             for(j=0;j<m;j++){
67                 scanf("%d",&Map[i][j]);
68                 Map[i][j]*=55;
69             }
70         s=0;
71         for(i=0;i<n;i++){
72             scanf("%d",&p[i]);
73             p[i]--;
74             s+=Map[i][p[i]]/55;
75             Map[i][p[i]]++;
76         }
77         ans=KM(n,m);
78         t=ans%55;
79         ans/=55;
80         printf("%d %d
",n-t,ans-s);
81     }
82     return 0;
83 }

View Code

hdu2853 Assignment 完美匹配 多校联赛的好题

hdu2853 Assignment 完美匹配多校联赛的好题