久闻公之大名
大概就是 把每个结果看成坐标为\(\sum a,\sum b\)的点，那么答案一定在这些点的左下凸壳上。
为了勾勒出凸包，我们可以先找到最左边和最下面的两个点，然后每次找到离当前两个点连线最远的点并分两边递归向下。
要找到最远的点，只要算出每个\(a,b\)的截距，那么只要截距最小即可。这个可以用KM算法来求。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// <3571.cpp> - Thu Feb 23 09:48:59 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <complex> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; typedef complex<int> pt; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int N=75; const int INF=1e9; #define forall() for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) int n,a[N][N],b[N][N],w[N][N]; int lx[N],ly[N],slack[N],mat[N]; bool vx[N],vy[N]; bool dfs(int x){ vx[x]=1; for(int i=1;i<=n;i++){ if(vy[i])continue; int k=lx[x]+ly[i]-w[x][i]; if(!k){ vy[i]=1; if(!mat[i]||dfs(mat[i]))return mat[i]=x; }else slack[i]=min(slack[i],k); } return 0; } pt km(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)lx[i]=max(lx[i],w[i][j]); ly[i]=mat[i]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)slack[j]=INF,vx[j]=vy[j]=0; while(!dfs(i)){ int d=INF; for(int j=1;j<=n;j++)if(!vy[j])d=min(d,slack[j]); for(int j=1;j<=n;j++)if(vx[j])lx[j]-=d; for(int j=1;j<=n;j++)if(vy[j])ly[j]+=d; for(int j=1;j<=n;j++)vx[j]=vy[j]=0; } } int ta=0,tb=0; for(int i=1;i<=n;i++)ta+=a[mat[i]][i],tb+=b[mat[i]][i]; return pt(ta,tb); } int work(pt l,pt r){ forall()w[i][j]=a[i][j]*(r.imag()-l.imag())-b[i][j]*(r.real()-l.real()); pt m=km(); if(l==m||m==r)return min(l.real()*l.imag(),r.real()*r.imag()); return min(work(l,m),work(m,r)); } int main(){ int T=gi(); while(T--){ n=gi(); forall()a[i][j]=gi(); forall()b[i][j]=gi(); forall()w[i][j]=-a[i][j]; pt l=km(); forall()w[i][j]=-b[i][j]; pt r=km(); printf("%d\n",work(l,r)); } return 0; } |
说点什么