[BZOJ]3060: [Poi2012]Tour de Byteotia-白红宇

[BZOJ]3060: [Poi2012]Tour de Byteotia

阅读量：5218 次

发布时间：2019-06-14

本文共 1706 字，大约阅读时间需要 5 分钟。

题解:首先我们忽略<=k这个条件可以得出每形成一个环就需要删掉一条边那么并查集搞一下就可以得出答案那么对于k的限制我们先把两点都大于k的边处理掉然后剩下的继续并查集搞一下就完了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=1e6+10;const double eps=1e-8;#define ll long longusing namespace std;struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}int f[MAXN];int find1(int x){ if(f[x]==x)return x; return f[x]=find1(f[x]);}typedef struct node{ int u,v;}node;node d[MAXN<<1];int main(){ int n=read(),m=read(),k=read(); inc(i,1,n)f[i]=i; int u,v;int ans=0,cnt=0; inc(i,1,m){ u=read();v=read(); if(u>k&&v>k){ int t1=find1(u);int t2=find1(v); if(t1!=t2)f[t1]=t2; } else d[++cnt]=(node){u,v}; } inc(i,1,cnt){ int t1=find1(d[i].u);int t2=find1(d[i].v); if(t1==t2)ans++; else f[t1]=t2; } printf("%d\n",ans); return 0;}

3060: [Poi2012]Tour de Byteotia

Time Limit: 30 Sec Memory Limit: 256 MB

Submit: 388 Solved: 254

[][][]

Description

给定一个

n个点

m条边的无向图，问最少删掉多少条边能使得编号小于等于

k的点都不在环上。

Input

第一行三个整数

n，

m，

k；

接下来

m行每行两个整数

a_i，

b_i，表示

a_i和

b_i之间有一条无向边。

Output

一个整数，表示最少的删边数量。

Sample Input

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

Sample Output

转载于:https://www.cnblogs.com/wang9897/p/10353178.html

你可能感兴趣的文章