CF1027F Session in BSU (并查集+树上构造)

题目大意：你可以在第$ai$天或者第$bi$天进行第$i$场考试，每天最多进行一场考试，求把所有考试都考完的最早结束时间

由于天数可能很大，需要离散

把问题抽象成一棵树，每个点最多被"分配"一条边，现在要删点

画画图可以发现

如果一个联通块是一棵树，那么可以删去至多一个点

如果一个联通块是一个单环树(n个点n条边)，那么一个点都不能删掉

如果一个联通块边数大于点数，会发现无法把每个点只分配一条边，不合法，输出-1

判树还是单环树，求一个联通块内点的度总和/2和点数比较即可

并查集维护一下点属于哪个联通块即可

注意点数是$2*10^6$而不是$1*10^6$

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 2000100

 #define maxn 100000

 #define ll long long

 #define mod 1000000007

 #define iset multiset<node>::iterator

 using namespace std;

 //re

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,m,K,ma,cte,num;

 int head[N],inc[N],id[N*],vis[N],fa[N],sum[N],sz[N],typ[N];

 struct E{int x,y;}e[N];

 struct Edge{int to,nxt,val;}edge[N*];

 void ae(int u,int v){

     cte++;edge[cte].to=v,inc[v]++;

     edge[cte].nxt=head[u],head[u]=cte;}

 int find_fa(int x){

     int y=x,pre;while(fa[y]!=y){y=fa[y];}

     while(fa[x]!=y){pre=fa[x],fa[x]=y,x=pre;}

     return y;

 }

 int dfs(int u)

 {

     vis[u]=;int ans=;

     for(int j=head[u];j;j=edge[j].nxt){

         int v=edge[j].to;

         if(vis[v]) continue;

         fa[v]=u,ans+=dfs(v),sz[u]+=sz[v];

     }sz[u]+=inc[u];return ans;

 }

 int main()

 {

     scanf("%d",&n);

     int x,y,z,fx;

     for(int i=;i<=n;i++)

         e[i].x=gint(),e[i].y=gint(),

         id[++num]=e[i].x,id[++num]=e[i].y;

     sort(id+,id+num+);

     num=unique(id+,id+num+)-(id+);

     for(int i=;i<=n;i++){

         x=lower_bound(id+,id+num+,e[i].x)-id;

         y=lower_bound(id+,id+num+,e[i].y)-id;

         ae(x,y),ae(y,x);

     }int tot;

     for(int i=;i<=num;i++) fa[i]=i;

     for(int i=;i<=num;i++)

         if(!vis[i]){

             sum[i]=dfs(i);

             if(sum[i]==(sz[i]+)/)

                 typ[i]=;

             else if(sum[i]==(sz[i]/))

                 typ[i]=;

             else{printf("-1\n");return ;}

         }

     int ans=num;

     for(int i=num;i>=;i--){

         fx=find_fa(i);

         if(typ[fx]==) {typ[fx]=;ans=i-;}

         else break;

     }

     printf("%d\n",id[ans]);

     return ;

 }

巴特西

CF1027F Session in BSU (并查集+树上构造)

最新文章

热门文章