题解 P4809 【[CCC 2018]最大战略储备】

༺請༒癌༻ · 2019-02-23 19:41:59 · 题解

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,p,q,a,b,c,fax[100010],fay[100010];
long long sum=0,ans=0;
struct E{
    int x,y,w,t;
}e[1000010];
int cmp(const E &a,const E &b) {
    return a.w<b.w;
}
int findx(int x) {
    if(x!=fax[x]) return fax[x]=findx(fax[x]);
    return fax[x];
}
int findy(int x) {
    if(x!=fay[x]) return fay[x]=findy(fay[x]);
    return fay[x];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&q);

    for(int i=1;i<=m;i++) fax[i]=i;
    for(int j=1;j<=n;j++) fay[j]=j; 

    for(int i=1;i<=p;i++) {
        scanf("%d%d%d",&a,&b,&c);
        e[i]=(E){a,b,c,0};
        sum+=1ll*e[i].w*n;
    }

    for(int i=1;i<=q;i++) {
        scanf("%d%d%d",&a,&b,&c);
        e[i+p]=(E){a,b,c,1};
        sum+=1ll*e[i+p].w*m;
    }

    sort(e+1,e+1+p+q,cmp);

    for(int i=1;i<=p+q;i++) {
        if(e[i].t) {
            int U=findy(e[i].x),V=findy(e[i].y);
            if(U!=V) {
                fay[U]=V;
                ans+=1ll*m*e[i].w;
                n--;
            }
        }
        else {
            int U=findx(e[i].x),V=findx(e[i].y);
            if(U!=V) {
                fax[U]=V;
                ans+=1ll*n*e[i].w;
                m--;
            }
        }
    }
    printf("%lld\n",sum-ans);
    return 0;
}