P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
考虑检出平面直角坐标系，以 \(\sum a_i\) 为 x 轴，\(\sum b_i\) 为 y 轴。
考虑先求出 \(A, B\) 分别为 \(x\) 轴最小的点，离 \(y\) 轴最小的点，这个我们可以使用最小生成树来解决。
然后我们发现等价于求一个在 \(A, B\) 下面的 \(C\) 使得 \(C\) 离 \(A, B\) 最大。
然后我们考虑这个就是让 \(S_{ACB}\) 最大。
\[S_{ACB} = \frac{-\vec{AB}\times\vec{AC}}{2}
\]
然后我们让 \(\vec{AB} \times \vec{AC}\) 求这个最小。然后我们直接拆叉积。
\[(x_B - x_A)y_C + (y_A - y_B)x_c + y_bx_a - x_by_a
\]
后面两个是常数不用管。然后我们要让前两项最小，对于这个直接带进去 \(w_{c, d} = (x_B - x_A)b_{c, d} + (y_A - y_B)a_{c, d}\) 求最小生成树即可。
然后我们用最小生成树可以求解出这一个 \(C\)，然后我们考虑这个 \(C\) 的分布是一个下凸包，然后我们每次考虑算完这个 \(C\) 判断 \(\vec{AB} \times \vec{AC} \geq 0\) 就退出即可。
然后我们对于每一种取值直接算最小 \(x * y\) 即可。
P3236 [HNOI2014] 画框
这个题也是照猫画虎，但是 \(w_{c, d} = -(x_B - x_A)b_{c, d} + (y_A - y_B)a_{c, d}\) 求二分图最大完备匹配即可。
可是我不会使用 KM 令人感慨。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define int long long
/*\yhx12243/ 鱼大保佑*/
using namespace std;
const int _ = 505;
const int inf = 1e16;
int T, n, m, res;
int a[_][_], b[_][_];
struct vec {
int x, y;
friend vec operator - (vec a, vec b) { return vec{a.x - b.x, a.y - b.y}; }
friend int operator * (vec a, vec b) { return (a.x * b.y - b.x * a.y); }
};
namespace KuhnMunkres {
int la[_], ra[_], w[_][_], vis[_], slk[_], mch[_], prv[_];
void init (int x, int y) {
rep(i, 1, n) rep(j, 1, n)
w[i][j] = -(x * a[i][j] + y * b[i][j]);
}
void bfs (int u) {
int x, y = 0, p = 0, dlt;
memset(prv, 0, sizeof(prv));
rep(i, 1, n) slk[i] = inf;
mch[y] = u;
while (1) {
x = mch[y], dlt = inf, vis[y] = 1;
rep(i, 1, n) {
if (vis[i]) continue ;
if (slk[i] > la[x] + ra[i] - w[x][i]) {
slk[i] = la[x] + ra[i] - w[x][i],
prv[i] = y;
}
if (slk[i] < dlt) dlt = slk[i], p = i;
}
rep(i, 0, n) {
if (vis[i]) {
la[mch[i]] -= dlt,
ra[i] += dlt;
} else slk[i] -= dlt;
} y = p;
if (mch[y] == -1) { break ; }
}
while(y) { mch[y] = mch[prv[y]]; y = prv[y]; }
}
vec KM () {
memset(mch, -1, sizeof(mch)),
memset(la, 0, sizeof(la)),
memset(ra, 0, sizeof(ra));
rep(i, 1, n) {
memset(vis, 0, sizeof(vis));
bfs(i);
}
vec ret;
ret = {0, 0};
rep(i, 1, n) if (mch[i] != -1) {
ret.x += a[mch[i]][i],
ret.y += b[mch[i]][i];
}
return ret;
}
}
void solve (vec a, vec b) {
KuhnMunkres :: init(a.y - b.y, b.x - a.x);
vec c = KuhnMunkres :: KM();
res = min(res, c.x * c.y);
if ((b - a) * (c - a) >= 0) return ;
solve(a, c), solve(c, b);
}
signed main () {
cin >> T;
while(T --) {
cin >> n;
rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
rep(i, 1, n) rep(j, 1, n) cin >> b[i][j];
vec x, y;
KuhnMunkres :: init(1, 0);
x = KuhnMunkres :: KM();
KuhnMunkres :: init(0, 1);
y = KuhnMunkres :: KM();
res = min(x.x * x.y, y.x * y.y);
solve(x, y);
cout << res << endl;
}
return 0;
}