题解 P3236 【[HNOI2014]画框】

Ameyax · 2018-03-05 18:32:54 · 题解

类似于最小乘积生成树，把一种匹配的\sum A_i和\sum B_i分别看作横纵坐标，然后找x \times y最小的点。
可以先找出x最小的点A和y最小的点B，然后找AB左下方离AB最远的点C，即\overrightarrow{AB}\times\overrightarrow{AC}最小。

那么把权值改成g[i][j]=(y_A-y_B)\times a[i][j]+(x_B-x_A)\times b[i][j]，再用二分图带权匹配就可以找出C。
找出C后用叉积判断C是不是在AB的下方，如果是，就递归解决线段AC和CB。
常数巨大的代码，之前写费用流还T了一次。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, u) for (int i = fir[u]; i; i = e[i].nxt)
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int inf = 50000000;
int T, n, ans, a[73][73], b[73][73];
struct Vector
{
    int x, y;
    Vector() {}
    Vector(int xx, int yy) { x = xx, y = yy; }
    friend Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
    friend int operator * (Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
};
struct Graph
{
    int g[73][73], lx[73], ly[73], sla[73], match[73];
    bool visx[73], visy[73];
    void build(int wx, int wy)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = -(wx * a[i][j] + wy * b[i][j]);
    }
    bool dfs(int u)
    {
        visx[u] = true;
        for (int v = 1; v <= n; v++) if (!visy[v])
        {
            int t = lx[u] + ly[v] - g[u][v];
            if (!t)
            {
                visy[v] = 1;
                if (!match[v] || dfs(match[v]))
                {
                    match[v] = u;
                    return true;
                }
            }
            else sla[v] = min(sla[v], t);
        }
        return false;
    }
    Vector km()
    {
        memset(lx, 0, sizeof lx);
        memset(ly, 0, sizeof ly);
        memset(match, 0, sizeof match);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                lx[i] = max(lx[i], g[i][j]);
        for (int i = 1; i <= n; i++)
        {
            memset(sla, 63, sizeof sla);
            while (true)
            {
                memset(visx, 0, sizeof visx);
                memset(visy, 0, sizeof visy);
                if (dfs(i)) break;
                int d = inf;
                for (int i = 1; i <= n; i++)
                    if (!visy[i]) d = min(d, sla[i]);
                for (int i = 1; i <= n; i++)
                    if (visx[i]) lx[i] -= d;
                for (int i = 1; i <= n; i++)
                    if (visy[i]) ly[i] += d;
                    else sla[i] -= d; 
            }
        }
        Vector re(0, 0);
        for (int i = 1; i <= n; i++)
            re.x += a[match[i]][i], re.y += b[match[i]][i];
        return re;
    }
} g;
void solve(Vector A, Vector B)
{
    g.build(A.y - B.y, B.x - A.x);
    Vector C = g.km();
    ans = min(ans, C.x * C.y);
    if ((B - A) * (C - A) >= 0) return;
    solve(A, C), solve(C, B);
}
int main()
{
    T = read();
    while (T--)
    {
        n = read();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                a[i][j] = read();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                b[i][j] = read();
        g.build(1, 0);
        Vector A = g.km();
        g.build(0, 1);
        Vector B = g.km();
        ans = min(A.x * A.y, B.x * B.y);
        solve(A, B);
        printf("%d\n", ans);
    }
    return 0;
}