CF1037E Trips (离线+图上构造)

题目大意：一共有n个人，每天早上会有两个人成为朋友，朋友关系不具有传递性，晚上，它们会组织旅游，如果一个人去旅游，那么他不少于$k$个朋友也要和他去旅游，求每天的最大旅游人数

一开始并没有想到反向建图，并查集搞了好久也没出解，看了题解的思路，大概是这样的

转化问题，反向建图，把正序往图里建边换成每次倒序在图里删边。

显然，一开始/删掉边之后，度小于K的点一定不可用，那么把它删掉，和它相连的边也删掉

那么可能这个点删掉以后，和它相连的某个点度也小于K了，再把那个点也删掉...发现这是一个类似于拓扑的过程

由于每个点只会被删掉1次，所以复杂度大约是$O(n+m)$

边全都加完的图中，也可能有些点既没有入度也没有出度，答案里要把它们去掉

 #include <set>

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 200100

 #define ll long long

 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,sum;

 int head[N],inc[N],ans[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;}

 queue<int>que;

 void Pop(int x)

 {

     que.push(x);

     while(!que.empty())

     {

         int x=que.front();que.pop();

         if(head[x]!=) sum--;

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

             if(edge[j].val==-)continue;

             edge[j].val=edge[j^].val=-;

             int v=edge[j].to;

             inc[v]--;

             if(inc[v]<K) que.push(v);

         }head[x]=;

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&K);

     int x,y,z;cte=;sum=n;

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

         x=gint(),y=gint(),ae(x,y),ae(y,x);

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

         if(head[i]==) sum--;

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

         if(inc[i]<K) Pop(i);

     for(int j=m;j>=;j--)

     {

         ans[j]=sum;

         if(edge[j<<].val==-)

         {continue;}

         x=edge[j<<].to;

         y=edge[j<<|].to;

         inc[x]--,inc[y]--;

         edge[j<<].val=edge[j<<|].val=-;

         if(inc[x]<K) Pop(x);

         if(inc[y]<K) Pop(y);

     }

     for(int j=;j<=m;j++)

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

     return ;

 }

巴特西

CF1037E Trips (离线+图上构造)

最新文章

热门文章