【LG3236】[HNOI2014]画框

题面

洛谷

题解

和这题一模一样。

将最小生成树换成\(KM\)即可。

关于复杂度，因为决策点肯定在凸包上，且\(n\)凸包的期望点数为\(\sqrt {\ln n}\)

所以\(n!\)个点的期望点数为\(\sqrt {\ln n!}=\sqrt {\sum_{i=1}^ni}\)

所以总复杂度\(O(\sqrt {\ln n!}*n^4)\)

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int INF = 1e9;

const int MAX_N = 100;

struct Point { int x, y; } ;

Point operator - (const Point &l, const Point &r) { return (Point){l.x - r.x, l.y - r.y}; }

int cross(const Point &l, const Point &r) { return l.x * r.y - l.y * r.x; }

int N, ans;

namespace Gra {

	int A[MAX_N][MAX_N], B[MAX_N][MAX_N];

    int g[MAX_N][MAX_N], lx[MAX_N], ly[MAX_N], sla[MAX_N], match[MAX_N];

    bool visx[MAX_N], visy[MAX_N];

    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;

    }

    Point 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 (1) {

                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;

            }

        }

        Point res = (Point){0, 0};

        for (int i = 1; i <= N; i++)

            res.x += A[match[i]][i], res.y += B[match[i]][i];

        return res;

    }

}

void Div(Point A, Point B) {

	Gra::build(A.y - B.y, B.x - A.x);

	Point C = Gra::KM();

	ans = min(ans, C.x * C.y);

	if (cross(B - A, C - A) >= 0) return ;

	Div(A, C), Div(C, B);

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	int T; scanf("%d", &T);

	while (T--) {

		scanf("%d", &N);

		for (int i = 1; i <= N; i++)

			for (int j = 1; j <= N; j++)

				scanf("%d", &Gra::A[i][j]);

		for (int i = 1; i <= N; i++)

			for (int j = 1; j <= N; j++)

				scanf("%d", &Gra::B[i][j]);

		Gra::build(1, 0);

		Point A = Gra::KM();

		Gra::build(0, 1);

		Point B = Gra::KM();

		ans = min(A.x * A.y, B.x * B.y);

		Div(A, B);

		printf("%d\n", ans);

	}

    return 0;

}