Manthan, Codefest 18 (rated, Div. 1 + Div. 2) E bfs + 离线处理

https://codeforces.com/contest/1037/problem/E

题意

有n个人,m天,在第i天早上,x和y会成为朋友,每天晚上大家都要上车,假如一个人要上车那么他得有至少k个朋友上车,输出每天晚上上车人数

题解

一个点的度数<k,他就上不了车
假如一个人上不了车,那么他对他的朋友就没有了价值,就等于把边去掉
离线处理,反着消边
因为每条边只能走一次,所以标记边bfs

代码

#include<bits/stdc++.h>

#define MAXN 200005

#define mk make_pair

using namespace std;

int n,m,k,u[MAXN][2],in[MAXN],a[MAXN];

vector<int>G[MAXN];

queue<int>Q;

map<pair<int,int>,int>del;

int main(){

	cin>>n>>m>>k;

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

		int x,y;

		scanf("%d%d",&x,&y);

		u[i][0]=x;u[i][1]=y;

		in[x]++;in[y]++;

		G[x].push_back(y);G[y].push_back(x);

	}

	int ans=n;

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

		if(in[i]<k){ans--;Q.push(i);}

	}

	while(!Q.empty()){

		int u=Q.front();Q.pop();

		for(auto v:G[u]){

			if(del[mk(u,v)]==1)continue;

			del[mk(u,v)]=del[mk(v,u)]=1;

			if(in[v]<k)continue;

			in[v]--;

			if(in[v]<k){ans--;Q.push(v);}

		}

	}

	a[m]=ans;

	for(int i=m;i>1&&ans>0;i--){

		int x=u[i][0],y=u[i][1];

		if(del[mk(x,y)]==1){a[i-1]=ans;continue;}

		del[mk(x,y)]=del[mk(y,x)]=1;

		in[x]--;in[y]--;

		if(in[x]<k){ans--;Q.push(x);}

		if(in[y]<k){ans--;Q.push(y);}

		while(!Q.empty()){

		int u=Q.front();Q.pop();

		for(auto v:G[u]){

			if(del[mk(u,v)]==1)continue;

			del[mk(u,v)]=del[mk(v,u)]=1;

			if(in[v]<k)continue;

			in[v]--;

			if(in[v]<k){ans--;Q.push(v);}

		}

	    }

		a[i-1]=ans;

	}

	for(int i=1;i<=m;i++)printf("%d\n",a[i]);

}

巴特西

Manthan, Codefest 18 (rated, Div. 1 + Div. 2) E bfs + 离线处理

题意

题解

代码

最新文章

热门文章