【tyvj2044】旅游景点

题目描述

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;
}