Lutece 2220 hqf吹泡泡

题目链接: https://acm.uestc.edu.cn/problem/hqfchui-pao-pao/description

分析:

最小生成树模板题。

显然对于一棵树来讲,删一条边变成两棵树,删两条边变成三棵树。

所以跑一个最小生成树出来,然后从权值最大的开始删即可。

我写了,一发A了,有什么好说的.jpg

代码:

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;

///////////////////////////
struct edge
{
    int u,v,cost;
    edge(){}
    edge(int _u,int _v,int _cost)
    {
        u=_u;v=_v;cost=_cost;
    }
    bool operator < (const edge &a) const
    {
        return cost > a.cost;
    }
};
priority_queue<edge> edges;
const int MAX_N=1001;
int par[MAX_N];
int ranks[MAX_N];
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
      par[i]=i;
      ranks[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)
    {
      return x;
    }
    else
    {
      return par[x]=find(par[x]);
    }
}
void unite(int x,int 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(int x,int y)
{
    return find(x)==find(y);
}
vector<int> mstcost;
int kruskal(int n)
{
    init(n);
    int sum=0;
    edge tmp;
    for(int i=0;i<n-1;)
    {
        tmp=edges.top();edges.pop();
        if(!same(tmp.u,tmp.v))
        {
            unite(tmp.u,tmp.v);
            sum+=tmp.cost;
            mstcost.push_back(tmp.cost);
            ++i;
        }
    }
    return sum;
}
////////

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m,k,u,v,w;
    cin>>n>>m>>k;
    for(int i=0;i<m;++i)
    {
        cin>>u>>v>>w;
        edges.push(edge(u,v,w));
    }
    int sum=kruskal(n);
    for(int i=0;i<k-1;++i)
    {
        sum-=mstcost[n-2-i];
    }
    cout<<sum<<endl;
    return 0;
}

发表评论

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