over 4 years ago

看了人家的代码还调了那么久真是……
最小乘积生成树:摘自http://blog.csdn.net/cjoilmd/article/details/7270482
利用数形结合的思想,每棵生成树在坐标系上对应的是点(sigma(a),sigma(b)), 那么,最小乘积生成树必定在某个k最小的反比例函数xy= k中。
先求出sigma(a)最小的点,sigma(b)最小的点,利用凸包思想,找离这两点所连成的直线最远(往靠近原点那边)的点(生成树)c,得到一个三角形,三角形内部的点是不如c优的,可以排除,然后递归处理a -->c ,c-->b的情况。
复杂度:不好确定……
那么如何确定往下分的点呢?
步骤:
1、将每个点乘以left->right的向量,做最小生成树。在求的过程中更新答案。
2、若答案在向量下边,就递归处理。

//注意一下long long 的转化 
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#define maxn 201

#define maxm 10001

using namespace std;
int n,m;
struct node
{int u,v,x,y;long long c;} a[maxm];
int fa[maxn];
struct point 
{int w1,w2;
 point(int x=0,int y=0){w1=x;w2=y;}
}ans;
bool cmp(const node a,const node b)
{
    return a.c<b.c;
}
int find(int x)
{
    if (fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
point kruskal()
{
    point temp;int i,x,y,tot=0;
    sort(a+1,a+m+1,cmp);
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<=m;i++)
    {
        x=find(a[i].u);y=find(a[i].v);
        if (x!=y)
        {
            tot++;fa[x]=y;
            temp.w1+=a[i].x;temp.w2+=a[i].y;
            if (tot==n-1) break;
        }
    }
    if (1ll*ans.w1*ans.w2>1ll*temp.w1*temp.w2||1ll*ans.w1*ans.w2==1ll*temp.w1*temp.w2&&ans.w1>temp.w1)  ans=temp;
    return temp;
}
long long cj(int x1,int y1,int x2,int y2){return 1ll*x1*y2-1ll*x2*y1;}
long long cross(point a,point b,point c){return cj(b.w1-a.w1,b.w2-a.w2,c.w1-a.w1,c.w2-a.w2);} 
void binary(point left,point right)
{
    int x=right.w1-left.w1,y=right.w2-left.w2,i,j;
    for (i=1;i<=m;i++) a[i].c=1ll*a[i].x*y-1ll*a[i].y*x;
    point mid=kruskal();
    if (cross(left,right,mid)<=0) return;
    binary(left,mid);binary(mid,right);
}
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') c=getchar(),bj=-1;
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
int main()
{
    int i,j,k;point left,right;
    ans.w1=ans.w2=1234567893;
    n=readln();m=readln();
    for (i=1;i<=m;i++)
    {a[i].u=readln()+1;a[i].v=readln()+1;
     a[i].x=readln();a[i].y=readln();
     a[i].c=a[i].x;}
    right=kruskal();
    for (i=1;i<=m;i++) a[i].c=a[i].y;
    left=kruskal();
    binary(left,right);//注意这里leftright的确定,相当于是按y轴划分。 
    printf("%d %d\n",ans.w1,ans.w2);
}
← 【spoj104】【生成树计数】highways 【bzoj2588】【spoj10628】【主席树】count on a tree →
 
comments powered by Disqus