给定一个$n$个点$m$条边的图，一条边有两个值$a$,$b$，求最小花费生成树，定义花费为这$n-1$条边的$a$值和这$n-1$条边的$b$值和。
将一个方案的答案$(\sum a,\sum b)$看作一个二维平面上的点。
则要求的即为最靠近左下的点。
那么开始先求出最靠近$x$轴和$y$轴的点（即按$a$为权值做一遍最小生成树和按$b$做一遍），记为$A$,$B$。
然后要求的便是离$AB$最远的$C$点($solve(A,B)$)，可以用叉积来判断。
也就是$\vec{CA}*\vec{CB}$最小，将$(x[i]-Ax,y[i]-Ay)*(x[i]-Bx,y[i]-By)$拆开，可以发现新的权值便为$x[i]*(Ay-By)+y[i]*(Bx-Ax)$，以此再做一遍最小生成树便能求出$C$，求出$C$的同时，与最优答案作比较，将更优的作为答案。
然后递归$solve(A,C),solve(C,B)$。
终止条件为$\vec{CA}*\vec{CB}>=0$ 叉积大于等于$0$，即不存在在$A,B$点左下角的点。
|
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 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; int n,m,f[210]; struct node{int u,v,a,b;ll w;}E[20010],a[20010]; struct Point { ll x,y;}ANS; ll Ans; Point operator - (Point a,Point b) { return (Point){a.x-b.x,a.y-b.y};} bool cmp(node a,node b) { return a.w<b.w;} ll cross(Point a,Point b) { return a.x*b.y-a.y*b.x;} int get(int x) { if (f[x]==x) return x;else f[x]=get(f[x]); return f[x]; } Point MST() { for (int i=1;i<=n;i++) f[i]=i; Point ans=(Point){0,0}; sort(a+1,a+m+1,cmp); int cnt=0; for (int i=1;i<=m;i++) { int x=get(a[i].u),y=get(a[i].v); if (x!=y) { f[x]=y; ans.x+=a[i].a; ans.y+=a[i].b; cnt++; } if (cnt==n-1) break; } if (ans.x*ans.y<Ans||(ans.x*ans.y==Ans&&ans.x<ANS.x)) Ans=ans.x*ans.y,ANS=ans; return ans; } void solve(Point A,Point B) { for (int i=1;i<=m;i++) a[i].w=(A.y-B.y)*a[i].a+(B.x-A.x)*a[i].b; Point C=MST(); if (cross(C-A,C-B)>=0) return; solve(A,C);solve(C,B); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].a,&E[i].b); E[i].u++;E[i].v++; } Ans=1LL<<60; ANS=(Point){1LL<<60,1LL<<60}; for (int i=1;i<=m;i++) a[i]=E[i],a[i].w=a[i].a; Point A=MST(); for (int i=1;i<=m;i++) a[i].w=a[i].b; Point B=MST(); solve(A,B); printf("%lld %lld\n",ANS.x,ANS.y); return 0; } |
