最小生成树系列

No.1 最小乘积生成树

所谓最小乘积生成树指的是每条边有k个权值，生成树的代价为
以k=2的情况为例：（多维的就是把线换成面）
送上题目链接一枚，请小心收好
我们把每一棵生成树看成二维平面上的一个点，Σw1看成横坐标，Σw2看成纵坐标…那么最小的定义就转化为了min(x*y)…也就是说每个点代表了一个反比例函数…很显然这个最优解一定存在于所有点的左下凸包上…
所以我们先找到最靠近x轴和最靠近y轴的两个点AB(这两个点一定是左下凸包上的点)…然后找到距离AB最远的靠近原点的C点(这个点也一定在凸包上)…然后再以AC、BC为界递归寻找凸包上的点…直到找不到点为止…

代码如下：
首先是我忘记了有重边用了prim…
然后是AB设成了全局变量…)

#include
#include
#include
#include
//by NeighThorn
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200+5,maxm=10000+5;
int n,m,cnt,fa[maxn],node[3][2],tmp[3][2],ansa,ansb;
long long ans;
struct M{
    int x,y,t,c,w;
    friend bool operator < (M a,M b){
        return a.wnow||(ans==now&&C.x=0)
        return;
    solve(A,C);solve(C,B);
}
signed main(void){
    scanf("%d%lld",&n,&m);
    for(int i=1,x,y,a,b;i<=m;i++)
        scanf("%d%d%d%d",&s[i].x,&s[i].y,&s[i].t,&s[i].c),s[i].x++,s[i].y++;
    ans=inf;
    for(int i=1;i<=m;i++)
        s[i].w=s[i].t;
    sort(s+1,s+m+1);G A=kruskal();
    for(int i=1;i<=m;i++)
        s[i].w=s[i].c;
    sort(s+1,s+m+1);G B=kruskal();
    solve(A,B);printf("%d %d\n",ansa,ansb);
    return 0;
}

No2. 最小方差生成树

题目戳这里
题解戳这里

代码如下：

#include
#include
#include
#include
#include
using namespace std;
const int maxn=100+5,maxm=2000+5;
int n,m,fa[maxn];double Min;
struct M{
    int x,y,w;
    double ww;
    friend bool operator < (M a,M b){
        return a.ww