CF76A Gift题解

Iceturky · 2024-07-05 10:21:03 · 题解

Link

考虑枚举其中一个最大值，然后求在这个最大值下另一个的最大值最小是多少。

后者就是一个每次插入一条边，求最小生成树。

最小生成树的边数是 \mathrm{O(n)} 级别的，且一条边在插入后若有一时刻不存在于最小生成树中，则永远不会出现在最小生成树上。

直接维护边集，插入排序，复杂度是 \mathrm{O(mn \alpha (n))} 。

code

const int N=2e2+5,M=5e4+5;

struct DSU{
    int fa[N],sum[N];
    void init(int n){
        for(int i=1;i<=n;i++)
            fa[i]=i,sum[i]=1; 
    }
    int fd(int x){
        return fa[x]==x?x:fa[x]=fd(fa[x]);
    }
    void merge(int x,int y){
        x=fd(x),y=fd(y);
        if(x!=y){
            if(sum[x]<sum[y])swap(x,y);
            fa[y]=x;
            sum[x]+=sum[y];
        }
    }
}D;

struct edge{
    int u,v,x,y;
    bool operator<(edge ano)const{
        return x<ano.x;
    }
}E[M],e[N];
int tot;
int n;
int tmp[N];

int mx;
bool tag;

void add(int id){
    for(int i=1;i<=tot+1;i++){
        if(e[i].y>E[id].y){
            tot++;
            for(int j=tot;j>=i;j--)
                swap(e[j],e[j+1]);
            e[i]=E[id];
            break;
        }
    }
//  for(int i=1;i<=tot;i++)
//      print(e[i].u),pc(' '),print(e[i].v),pc(' '),print(e[i].x),pc(' '),print(e[i].y),pc('\n');
    D.init(n);
    int cnt=0;
    mx=0;
    tag=0;
    for(int i=1;i<=tot;i++){
        int u=e[i].u,v=e[i].v;
        if(D.fd(u)!=D.fd(v)){
            mx=e[i].y;
            D.merge(u,v);
            tmp[++cnt]=i;
        }
    }
    if(cnt==n-1)
        tag=1;
    for(int i=1;i<=cnt;i++)
        e[i]=e[tmp[i]];
    tot=cnt;
    e[tot+1].y=inf;
}

signed main(){
    n=read();int m=read(),X=read(),Y=read();
    for(int i=1;i<=m;i++)
        E[i]={read(),read(),read(),read()};
    sort(E+1,E+1+m);
    int ans=inf;
    e[1].y=inf;
    for(int i=1;i<=m;i++){
        int j=i;
        while(j<=m&&E[j].x==E[i].x)
            add(j++);
        if(tag)
            ans=min(ans,E[i].x*X+mx*Y);
        i=j-1;
    }print(ans>=inf-2?-1:ans),pc('\n');
    return 0;
}