题目是要求最小乘积最小权匹配，

将一种方案看做一个二维点(x,y),x=a值的和，y=b值的和，所有方案中只有在下凸壳上的点才有可能成为最优解

首先要求出两端的方案l,r两个点

l就是a值的和最小的方案，

r就是b值的和最小的方案

然后递归work(l,r)即可得出所有在下凸壳上的点

work(l,r){

  找到一个离lr这条直线最远的且靠近原点的点mid

  如果l,mid,r构成下凸壳{

    work(l,mid)

    work(mid,r)

  }

}

如何找mid？

把所有边边权设为(a[i],b[i])它lr直线垂线上的投影，再求普通的最小权匹配即可。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int inf=~0U>>2,N=150,M=100110;struct P{int x,y;P(){x=y=0;}P(int _x,int _y){x=_x,y=_y;}P operator-(const P&a){return P(x-a.x,y-a.y);}}L,R;inline int cross(P a,P b){return a.x*b.y-a.y*b.x;}int n,m,i,j,w[N][N],wa[N][N],wb[N][N],test,ans;int u[M],v[M],c[M],co[M],coa[M],cob[M],nxt[M],t,S,T,l,r,q[M],g[N],f[N],d[N];bool in[N];inline void add(int x,int y,int z,int zo,int zoa,int zob){  u[++t]=x;v[t]=y;c[t]=z;co[t]=zo;coa[t]=zoa;cob[t]=zob;nxt[t]=g[x];g[x]=t;  u[++t]=y;v[t]=x;c[t]=0;co[t]=-zo;coa[t]=-zoa;cob[t]=-zob;nxt[t]=g[y];g[y]=t;}inline bool spfa(){  memset(d,127,sizeof d);d[S]=0;in[S]=1;l=r=M>>1;q[l]=S;  int x,i;  while(l<=r){    int x=q[l++];    if(x==T)continue;    for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]
        
         0)work(l,mid),work(mid,r);}int solve(){  ans=~0U>>1;  scanf("%d",&n);  for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&wa[i][j]);  for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&wb[i][j]);  for(i=1;i<=n;i++)for(j=1;j<=n;j++)w[i][j]=wa[i][j];  L=mincostflow();  for(i=1;i<=n;i++)for(j=1;j<=n;j++)w[i][j]=wb[i][j];  R=mincostflow();  work(L,R);  printf("%d\n",ans);}int main(){  scanf("%d",&test);  while(test--)solve();  return 0;}