Lutece 2215 oydy的征途I

题目链接: https://acm.uestc.edu.cn/problem/oydyde-zheng-tu-i/description

分析:

先跑一个最小生成树出来。

接下来的思路和次小生成树有点类似,先选择一条边然后找能替代它的边。

题目要求最小费用,所以必然是选择边权最大的边,然后寻找边权比它大且能够替代它的边。

有一个判断的技巧,就是把最大边权的边删去,然后再判断连通性。

这样子能大大减少码量。

最小生成树复杂度O(ElogE),并查集复杂度可以忽略不计,最多有E-V+1个未使用的边,所以总的复杂度为O(ElogE)。

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
const long long INF = 0x3f3f3f3f;

///////////////////////////
const long long MAX_N=100001;
long long par[MAX_N];
long long ranks[MAX_N];
void init(long long n)
{
    for(long long i=0;i<n;i++)
    {
        par[i]=i;
        ranks[i]=0;
    }
}
long long find(long long x)
{
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
}
void unite(long long x,long long y)
{
    x=find(x);y=find(y);
    if(x==y)return;
    if(ranks[x]<ranks[y])
    {
        par[x]=y;
    }
    else
    {
        par[y]=x;
        if(ranks[x]==ranks[y])ranks[x]++;
    }
}
bool same(long long x,long long y)
{
    return find(x)==find(y);
}

struct edge
{
    long long u,v,cost;
    edge(){}
    edge(long long _u,long long _v,long long _cost)
    {
        u=_u;v=_v;cost=_cost;
    }
    bool operator < (const edge &a) const
    {
        return cost > a.cost;
    }
};
priority_queue<edge> edges,used1,used2;
long long n,m,maxedge=0;
long long kruskal()
{
    init(n+1);
    long long sum=0;
    long long len=edges.size();
    edge tmp;
    for(long long i=0;i<len;++i)
    {
        tmp=edges.top();edges.pop();
        if(!same(tmp.u,tmp.v))
        {
            unite(tmp.u,tmp.v);
            sum+=tmp.cost;
            maxedge=max(maxedge,tmp.cost);
            used1.push(tmp);
        }
        else
        {
            used2.push(tmp);
        }
    }
    return sum;
}
////////
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    long long u,v,w;
    for(long long i=0;i<m;++i)
    {
        cin>>u>>v>>w;
        edges.push(edge{u,v,w});
    }
    long long nowsum=kruskal();
    long long fangan=0;
    nowsum-=maxedge;
    init(n+1);
    long long len=used1.size();
    edge tmp;
    for(long long i=0;i<len;++i)
    {
        tmp=used1.top();used1.pop();
        if(tmp.cost!=maxedge)
        {
            unite(tmp.u,tmp.v);
        }
        else
        {
            ++fangan;
        }
    }
    len=used2.size();
    for(long long i=0;i<len;++i)
    {
        tmp=used2.top();used2.pop();
        if(!same(tmp.u,tmp.v))
        {
            ++fangan;
        }
    }
    cout<<nowsum<<" "<<fangan;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注