題面

題解

這又是一種套路啊233

將\(\sum a_i\)和\(\sum b_i\)分別看做\(x\)和\(y\)，投射到平面直角坐標(biāo)系中，于是就是找\(xy\)最小的點

于是可以先找出\(x\)最小的點\(\mathrm{A}\)和\(y\)最小的點\(\mathrm{B}\)，然后找到在\(\mathrm{AB}\)下方的最遠(yuǎn)的點\(\mathrm{C}\)

即\(\overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{AC}}\)最小
\[ \begin{aligned} \because \overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{AC}} &= (x_{\mathrm{B}} - x_{\mathrm{A}})(y_{\mathrm{C}} - y_{\mathrm{A}}) - (y_{\mathrm{B}} - y_{\mathrm{A}})(x_\mathrm{C} - x_\mathrm{A}) \\ &= (x_\mathrm B - x_\mathrm A) \times y_\mathrm C + (y_\mathrm A - y_\mathrm B) \times x_\mathrm C + y_\mathrm B x_\mathrm A - x_\mathrm B y_\mathrm A \end{aligned} \]
于是將權(quán)值改成\(\mathrm{g}[i][j] = (y_\mathrm A - y_\mathrm B) \times a[i][j] + (x_\mathrm B - x_\mathrm A)\times b[i][j]\)，然后用\(\mathrm{KM}\)找出\(\mathrm C\)。

找到\(\mathrm C\)之后用叉積判斷一下\(\mathrm C\)是不是在\(\mathrm{AB}\)的下方，如果是的話，就遞歸處理\(\mathrm{AC, CB}\)

復(fù)雜度\(\mathrm{O}(\)能過\()\)

代碼

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<climits> #define RG register #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define clear(x, y) memset(x, y, sizeof(x))inline int read() {int data = 0, w = 1; char ch = getchar();while(ch != '-' && (!isdigit(ch))) ch = getchar();if(ch == '-') w = -1, ch = getchar();while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();return data * w; }const int N(75); int T, n, a[N][N], b[N][N], ans; struct vector { int x, y; }; inline vector operator - (const vector &lhs, const vector &rhs){ return (vector) {lhs.x - rhs.x, lhs.y - rhs.y}; } inline int operator * (const vector &lhs, const vector &rhs){ return lhs.x * rhs.y - lhs.y * rhs.x; } int g[N][N], lx[N], ly[N], visx[N], visy[N], match[N]; bool hungary(int x) {visx[x] = 1;for(RG int to = 1; to <= n; to++)if(!visy[to] && lx[x] + ly[to] == g[x][to]){visy[to] = true;if(!match[to] || hungary(match[to])) return (match[to] = x, true);}return false; }void build(int valx, int valy) {for(RG int i = 1; i <= n; i++) for(RG int j = 1; j <= n; j++)g[i][j] = -(valx * a[i][j] + valy * b[i][j]); }vector KM() {for(RG int i = 1; i <= n; i++)ly[i] = 0, lx[i] = *std::max_element(g[i] + 1, g[i] + n + 1);memset(match, 0, sizeof match);for(RG int x = 1; x <= n; x++)while(1){clear(visx, 0), clear(visy, 0);if(hungary(x)) break;int inc = INT_MAX;for(RG int i = 1; i <= n; i++) if(visx[i])for(RG int j = 1; j <= n; j++) if(!visy[j])inc = std::min(inc, lx[i] + ly[j] - g[i][j]);for(RG int i = 1; i <= n; i++) if(visx[i]) lx[i] -= inc;for(RG int i = 1; i <= n; i++) if(visy[i]) ly[i] += inc;}vector ans = (vector) {0, 0};for(RG int i = 1; i <= n; i++)ans.x += a[match[i]][i], ans.y += b[match[i]][i];return ans; }void solve(const vector &A, const vector &B) {build(A.y - B.y, B.x - A.x);vector C = KM(); ans = std::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(RG int i = 1; i <= n; i++)for(RG int j = 1; j <= n; j++)a[i][j] = read();for(RG int i = 1; i <= n; i++)for(RG int j = 1; j <= n; j++)b[i][j] = read();build(1, 0); vector A = KM();build(0, 1); vector B = KM();ans = std::min(A.x * A.y, B.x * B.y);solve(A, B); printf("%d\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cj-xxz/p/10395705.html

總結(jié)

以上是生活随笔為你收集整理的【HNOI2014】画框的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。