BZOJ 3571 画框 KM算法最小乘积最大权匹配

　　题意

　　　　有n个画框和n幅画。若第i幅画和第j个画框配对，则有平凡度A_ij和违和度B_ij，一种配对方案的总体不和谐度为∑A_ij*∑B_ij。求通过搭配能得到的最小不和谐度是多少。 n <= 70.

　　分析

　　　　这题是最小乘积最大权匹配裸题，其做法类似最小乘积生成树。

　　　　每个方案可以表示为二维平面上的点，答案必然在下凸壳上。

　　　　具体要怎么找呢？其实是有一个这样的方法：找出横坐标或纵坐标最小的点a和b，找点的方法可以用KM。

　　　　找到这两个点就可以分治下去做了，找到离直线ab距离最大的点（当然要在直线ab下方）。

　　　　列出点线距离公式，由于要找的点是在直线ab的下方，那么绝对值就可以去掉，整理为Ax+By的最值，然后就化成了一维，继续用KM来找，如此递归下去做。

　　　　当然，最小乘积XXX的东西似乎都可以用上面的方法做，拓展到多维方法也是类似的。

　　程序

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 #include <iostream>
  7 
  8 using namespace std;
  9 
 10 const int maxn = 75;
 11 const int INF = 0x3fffffff;
 12 bool visx[maxn], visy[maxn];
 13 int linker[maxn], slack[maxn], lx[maxn], ly[maxn], w[maxn][maxn];
 14 int n, a[maxn][maxn], b[maxn][maxn];
 15 struct Point
 16 {
 17     int x, y;
 18     Point (int x = 0, int y = 0):
 19         x(x), y(y) {}
 20     bool operator == (const Point &AI) const
 21     {
 22         return AI.x == x && AI.y == y;
 23     }
 24 };
 25 
 26 bool dfs(int x)
 27 {
 28     int y, temp;
 29     visx[x] = true;
 30     for (y = 1; y <= n; ++y)
 31     {
 32         if (visy[y]) continue ;
 33         temp = lx[x]+ly[y]-w[x][y];
 34         if (temp == 0)
 35         {
 36             visy[y] = true;
 37             if (linker[y] == -1 || dfs(linker[y]))
 38             {
 39                 linker[y] = x;
 40                 return true;
 41             }
 42         }
 43         else if (temp < slack[y]) slack[y] = temp;
 44     }
 45     return false;
 46 }
 47 
 48 Point KM()
 49 {
 50     int i, j, x, y, d;
 51     memset(ly, 0, sizeof(ly));
 52     memset(linker, -1, sizeof(linker));
 53     for (i = 1; i <= n; ++i)
 54     {
 55         lx[i] = -INF;
 56         for (j = 1; j <= n; ++j) lx[i] = max(lx[i], w[i][j]);
 57     }
 58     for (x = 1; x <= n; ++x)
 59     {
 60         for (y = 1; y <= n; ++y) slack[y] = INF;
 61         while (1)
 62         {
 63             memset(visx, 0, sizeof(visx));
 64             memset(visy, 0, sizeof(visy));
 65             if (dfs(x)) break ;
 66             d = INF;
 67             for (y = 1; y <= n; ++y) if (!visy[y]) d = min(d, slack[y]);
 68             for (i = 1; i <= n; ++i) if (visx[i]) lx[i] -= d;
 69             for (y = 1; y <= n; ++y)
 70                 if (visy[y]) ly[y] += d;
 71                 else slack[y] -=d;
 72         }
 73     }
 74     Point temp(0, 0);
 75     for (i = 1; i <= n; ++i)
 76         temp.x += a[linker[i]][i], temp.y += b[linker[i]][i];
 77     return temp;
 78 }
 79 
 80 int solve(Point p1, Point p2)
 81 {
 82     for (int i = 1; i <= n; ++i)
 83         for (int j = 1; j <= n; ++j)
 84             w[i][j] = (p2.y-p1.y)*a[i][j]+(p1.x-p2.x)*b[i][j];
 85     Point t = KM();
 86     if (t == p1 || t == p2) return min(p1.x*p1.y, p2.x*p2.y);
 87     return min(solve(p1, t), solve(t, p2));
 88 }
 89 
 90 int main()
 91 {
 92     freopen("a.in", "r", stdin);
 93     freopen("a.out", "w", stdout);
 94     int T;
 95     scanf("%d", &T);
 96     while (T --)
 97     {
 98         scanf("%d", &n);
 99         for (int i = 1; i <= n; ++i)
100             for (int j = 1; j <= n; ++j)
101                 scanf("%d", &a[i][j]);
102         for (int i = 1; i <= n; ++i)
103             for (int j = 1; j <= n; ++j)
104                 scanf("%d", &b[i][j]);
105         Point p1, p2;
106         for (int i = 1; i <= n; ++i)
107             for (int j = 1; j <= n; ++j)
108                 w[i][j] = -a[i][j];
109         p1 = KM();
110         for (int i = 1; i <= n; ++i)
111             for (int j = 1; j <= n; ++j)
112                 w[i][j] = -b[i][j];
113         p2 = KM();
114         printf("%d
", solve(p1, p2));
115     }
116     return 0;
117 }

View Code

BZOJ 3571 画框 KM算法 最小乘积最大权匹配

BZOJ 3571 画框 KM算法最小乘积最大权匹配