题目链接

题解

如果知道最小乘积生成树，那么这种双权值乘积最小就是裸题了

将两权值和作为坐标，转化为二维坐标系下凸包上的点，然后不断划分分治就好了

这里求的是最小匹配值，每次找点套一个二分图最小权匹配

为什么用KM算法？因为这道题丧心病狂卡费用流QAQ

写完就A啦，十分的感人

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<
         
          <<' '; puts("");using namespace std;const int maxn = 75,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int n,X[maxn][maxn],Y[maxn][maxn];int w[maxn][maxn],expa[maxn],expb[maxn],cp[maxn],visa[maxn],visb[maxn],dl[maxn];struct point{int x,y;}ans;inline point operator -(const point& a,const point& b){ return (point){a.x - b.x,a.y - b.y};}inline LL operator *(const point& a,const point& b){ return 1ll * a.x * b.y - 1ll * a.y * b.x;}inline bool operator <(const point& a,const point& b){ return 1ll * a.x * a.y == 1ll * b.x * b.y ? a.x < b.x : 1ll * a.x * a.y < 1ll * b.x * b.y;}bool dfs(int u){ visa[u] = true; REP(i,n) if (!visb[i]){ int kl = expa[u] + expb[i] - w[u][i]; if (!kl){ visb[i] = true; if (!cp[i] || dfs(cp[i])) {cp[i] = u; return true;} } else dl[i] = min(dl[i],kl); } return false;}point km(){ REP(i,n) expa[i] = -INF,expb[i] = cp[i] = 0; REP(i,n) REP(j,n) expa[i] = max(expa[i],w[i][j]); REP(i,n){ REP(j,n) dl[j] = INF; while (true){ REP(j,n) visa[j] = visb[j] = false; if (dfs(i)) break; int kl = INF; REP(j,n) if (!visb[j]) kl = min(kl,dl[j]); REP(j,n){ if (visa[j]) expa[j] -= kl; if (visb[j]) expb[j] += kl; else dl[j] -= kl; } } } point re; re.x = re.y = 0; REP(i,n) re.x += X[cp[i]][i],re.y += Y[cp[i]][i]; if (re < ans) ans = re; return re;}void solve(point A,point B){ REP(i,n) REP(j,n) w[i][j] = -((A.y - B.y) * X[i][j] + (B.x - A.x) * Y[i][j]); point C = km(); if ((C - A) * (B - A) <= 0) return; solve(A,C); solve(C,B);}int main(){ int T = read(); while (T--){ n = read(); ans.x = INF; ans.y = INF; REP(i,n) REP(j,n) X[i][j] = read(); REP(i,n) REP(j,n) Y[i][j] = read(); REP(i,n) REP(j,n) w[i][j] = -X[i][j]; point A = km(); REP(i,n) REP(j,n) w[i][j] = -Y[i][j]; point B = km(); solve(A,B); printf("%d\n",ans.x * ans.y); } return 0;}