当前位置:   article > 正文

【tyvj2044】旅游景点

经过调查,发现公园有 n 个景点,为了显示景点之间的优越性,我们按照 1,2,…, n 来

题目描述

liouzhou_101住在柳侯公园附近,闲暇时刻都会去公园散散步。
很那啥的就是,柳侯公园的道路太凌乱了,假若不认识路就会走着走着绕回原来的那条路。
liouzhou_101就开始自己YY,假若给他当上那啥管理者,就会想尽量减少道路回圈的个数,但是大范围的改变道路终归不是什么良策。
经过调查,发现公园有N个景点,为了显示景点之间的优越性,我们按照1,2,…,N来把这N个景点编号,当然编号越小就说明越重要。
为了显示自己的英明决策,liouzhou_101决定,前K重要的景点最为重要,当然他们是标号为1…K了的。需要保证这K个景点不在任何一个环上,原因很简单,这前K个景点是很重要的景点,参观的人也很多,自然不会希望参观的人因为在兜圈子而迷路吧。
于是,我们所能够做的就是把之前建造好的一些道路清除掉,使得保证前K重要的景点不在任何一个环上。


输入

第一行包括三个正整数 N,M 和 K,N 表示景点的数量,M 表示公园里的路径条
数,K 表示前 K 个景点最为重要。
再接下来 M 行,每行有两个正整数 x 和 y,表示景点 x 和景点 y 之间有一条边。


输出

仅一行,输出至少去除多少条路径,使得前 K 个重要的景点不在任何一个环上。


样例输入

11 13 5 
1 2 
1 3 
1 5 
3 5 
2 8 
4 11 
7 11 
6 10 
6 9 
2 3 
8 9 
5 9 
9 10


样例输出

3

 



题解

并查集,先把超过k的点所连的边连起来,这些是不会影响前k个点的。然后再把不在一个集合的点连起来,计算最多能连多少条边,然后总边数减去最多连的边就是答案。

 

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=100000+50;
const int maxm=200000*2+50;

int n,m,k,fat[maxn],ans,x,y,t;

struct node{int x,y;}a[maxm];

int father(int x){
    if(x!=fat[x]) fat[x]=father(fat[x]);
    return fat[x];
}

void un(int x,int y){
    int fa=father(x);
    int fb=father(y);
    if(fa!=fb) fat[fa]=fb;
}

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

int main(){
    read(n),read(m),read(k);
    for(int i=1;i<=n;i++) fat[i]=i;
    for(int i=1;i<=m;i++){
        read(a[i].x),read(a[i].y);
        if(a[i].x>a[i].y) swap(a[i].x,a[i].y);
        if(a[i].x>k&&a[i].y>k){
            un(a[i].x,a[i].y);
            ans++;
        }
    }
    for(int i=1;i<=m;i++){
        if(father(a[i].x)!=father(a[i].y)){
            un(a[i].x,a[i].y);ans++;
        }
    }
    cout<<m-ans<<endl;
    return 0;
}

 

转载于:https://www.cnblogs.com/rlddd/p/9679091.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/619455
推荐阅读
相关标签
  

闽ICP备14008679号