bzoj2395[Balkan 2011]Timeismoney最小乘积生成…

2018-06-17 23:54:53来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

所谓最小乘积生成树,即对于一个无向连通图的每一条边均有两个权值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

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:OpenGL显示图片

下一篇:C/C++ 一些常用的运算符