bzoj2395[Balkan 2011]Timeismoney最小乘積生成樹，bzoj2395
所謂最小乘積生成樹，即對於一個無向連通圖的每一條邊均有兩個權值xi，yi，在圖中找一顆生成樹，使得Σxi*Σyi取最小值。
直接處理問題較為棘手，但每條邊的權值可以描述為一個二元組（xi,yi），這也就不難想到將生成樹轉化為平面內的點，x代表Σxi，y代表Σyi（注意這裡的xi，yi指的是在生成樹中的邊的權值），那麼問題就變成了在平面內找一個點使得x*y最小，那麼顯然這個點是在下凸殼上的。
因此可以首先找出兩個一定在凸包上的點，例如A（minx，y），B（miny，x），在直線AB下方找一個在凸包上且x*y最小的點。
於是可以每次找距離直線AB最遠的點，有兩種求法，令找到的那個點為C，如果利用叉乘，即使向量CB叉乘向量CA最大，因為我們考慮的是向量的模長，可以讓向量CA叉乘向量CB（雖然模長是負的，但並沒有什麼關系，當然也可以最大化這個值，只不過一個是最小生成樹，一個是最大生成樹而已），然後最小化這個值即可。
2S=（B.x-A.x）（C.y-B.y）-（B.y-A.y）（C.x-A.x）省略常數後就變成了B.x*C.y-A.x*C.y-B.y*C.x+A.y*C.x。
因為只需要求Σxi，Σyi，因此只需要求出點的坐標，並不要考慮面積，所以將每條邊的yi=yi*（B.x-A.x），xi=xi*（A.y-B.y），以（xi+yi）為關鍵字排序kruskal（）就行了。
然後遞歸處理，直到叉積大於等於0退出（此時AB下方一定沒有點）
也可以利用點到直線的距離公式|Ax0+By0+C|/(√(A2+B2）），省略常數且保證B<=0,那麼若點在直線下方，則Ax+By+C>0。
因此可以省略絕對值符號，再省略常數，即使Ax0+By0最大，因此xi=xi*A，yi=yi*B，將（xi+yi）為關鍵字排序作最大生成樹即可，還是按叉積判斷（理應也可以看C.x*A+C.y*B<=0就退出，然而狂WA不止。。。。並不知道這是為什麼。。。。）
然後這是一道裸題，就可以愉快地切掉了。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 #define maxn 10100
8 #define inf 0x7fffffff
9
10 int n,m;
11 int val[2*maxn],fa[maxn];
12
13 struct edge{
14 int from,to,x,y;
15 long long z;
16 }e[maxn];
17
18 struct node{
19 int x,y;
20 long long calc(){return (long long)x*y;}
21 }minx,miny,ans;
22
23 int find(int x){
24 return fa[x]==x?x:fa[x]=find(fa[x]);
25 }
26
27 node kruskal(){
28 int tot=0;node now={0,0};
29 for (int i=1;i<=n;i++) fa[i]=i;
30 for (int i=1;i<=m;i++){
31 int a=find(e[i].from),b=find(e[i].to);
32 if (a!=b){
33 fa[a]=b;
34 tot++;
35 now.x+=e[i].x;
36 now.y+=e[i].y;
37 if (tot==n-1) break;
38 }
39 }
40 long long tmpa=ans.calc(),tmpb=now.calc();
41 if (tmpb<tmpa||(tmpb==tmpa&&now.x<ans.x)) ans=now;
42 return now;
43 }
44
45 long long cross(node a,node b,node c){
46 long long x1=(b.x-a.x),x2=(b.y-a.y),y1=(c.x-a.x),y2=(c.y-a.y);
47 return (x1*y2-x2*y1);
48 }
49
50 bool cmpx(edge a,edge b){return a.x<b.x;}
51 bool cmpy(edge a,edge b){return a.y<b.y;}
52 bool cmpz(edge a,edge b){return a.z<b.z;}
53
54 void solve(node a,node b){
55 for (int i=1;i<=m;i++)
56 e[i].z=e[i].y*(b.x-a.x)+e[i].x*(a.y-b.y);
57 sort(e+1,e+m+1,cmpz);
58 node t=kruskal();
59 if (cross(a,b,t)>=0) return;
60 solve(a,t);
61 solve(t,b);
62 }
63
64 int main(){
65 scanf("%d%d",&n,&m);
66 ans=(node){inf,inf};
67 for (int i=1,u,v;i<=m;i++) scanf("%d%d%d%d",&u,&v,&e[i].x,&e[i].y),e[i].from=++u,e[i].to=++v;
68 sort(e+1,e+m+1,cmpx);
69 minx=kruskal();
70 sort(e+1,e+m+1,cmpy);
71 miny=kruskal();
72 //cout<<minx.x<<' '<<minx.y<<' '<<miny.x<<' '<<miny.y<<endl;
73 solve(minx,miny);
74 printf("%d %d",ans.x,ans.y);
75 return 0;
76 }
View Code1
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 #define maxn 10100
8 #define inf 0x7fffffff
9
10 int n,m;
11 int val[2*maxn],fa[maxn];
12
13 struct edge{
14 int from,to,x,y;
15 long long z;
16 }e[maxn];
17
18 struct node{
19 int x,y;
20 long long calc(){return (long long)x*y;}
21 }minx,miny,ans;
22
23 int find(int x){
24 return fa[x]==x?x:fa[x]=find(fa[x]);
25 }
26
27 node kruskal(){
28 int tot=0;node now={0,0};
29 for (int i=1;i<=n;i++) fa[i]=i;
30 for (int i=1;i<=m;i++){
31 int a=find(e[i].from),b=find(e[i].to);
32 if (a!=b){
33 fa[a]=b;
34 tot++;
35 now.x+=e[i].x;
36 now.y+=e[i].y;
37 if (tot==n-1) break;
38 }
39 }
40 long long tmpa=ans.calc(),tmpb=now.calc();
41 if (tmpb<tmpa||(tmpb==tmpa&&now.x<ans.x)) ans=now;
42 return now;
43 }
44
45 int cross(node a,node b,node c){
46 int x1=b.x-a.x,y1=b.y-a.y,x2=c.x-a.x,y2=c.y-a.y;
47 return (x1*y2-x2*y1);
48 }
49
50 bool cmpx(edge a,edge b){return a.x<b.x;}
51 bool cmpy(edge a,edge b){return a.y<b.y;}
52 bool cmpz(edge a,edge b){return a.z>b.z;}
53
54 void solve(node a,node b){
55 int A=b.y-a.y,B=a.x-b.x;
56 for (int i=1;i<=m;i++) e[i].z=e[i].x*A+e[i].y*B;
57 sort(e+1,e+m+1,cmpz);
58 node t=kruskal();
59 if (cross(a,b,t)<0) solve(a,t),solve(t,b);
60 }
61
62 int main(){
63 // freopen("data.in","r",stdin);
64 // freopen("WA.out","w",stdout);
65 scanf("%d%d",&n,&m);
66 ans=(node){inf,inf};
67 for (int i=1,u,v;i<=m;i++) scanf("%d%d%d%d",&u,&v,&e[i].x,&e[i].y),e[i].from=++u,e[i].to=++v;
68 sort(e+1,e+m+1,cmpx);
69 minx=kruskal();
70 sort(e+1,e+m+1,cmpy);
71 miny=kruskal();
72 //cout<<minx.x<<' '<<minx.y<<' '<<miny.x<<' '<<miny.y<<endl;
73 solve(minx,miny);
74 printf("%d %d",ans.x,ans.y);
75 return 0;
76 }
View Code2
