P16007 [CCO 2016 Day 1] Field Trip 郊游

形式化题意

给出一张不一定联通的图，其中所有点的最大度数为 $2$，把这张图分割为数个连通块，使大小为 $k$ 的连通块数量最多。求最多能分出几个大小为 $k$ 的连通块以及需要删除的边的最小个数。

分析

由于所有点的最大度数为 $2$，所以该图的所有联通子图不是链就是环。大小小于 $k$ 的联通子图显然是没用的。

当子图大小等于 $k$ 时，直接加上就行了。无需删除任何边。

对于一条大小大于 $k$ 的链，不妨设它的大小为 $k_0$。我们可以把它分割成 $\lfloor \frac{k_0}{k} \rfloor$ 个大小为 $k$ 的链。显然这需要删除 $\lfloor \frac{k_0}{k} \rfloor - [k_0 \bmod k = 0]$ 条边。

对于一条大小大于 $k$ 的环，不妨设它的大小为 $k_1$。我们可以先随意删除一条边把它变成链。于是可以把它分割成 $\lfloor \frac{k_1}{k} \rfloor$ 个大小为 $k$ 的链，需要删除$\lfloor \frac{k_1}{k} \rfloor - [k_1 \bmod k = 0] + 1$ 条边。

做法

$1 \le N \le 10^6,0 \le M \le 10^6,1 \le K \le N$

显然需要 $O(n)$ 做法。我们可以跑一遍 DFS 来统计环、链及其大小，将这些数据存到一个点上，最后进行统计。

代码

#include <iostream>
#include <vector>
using namespace std;
vector <long long> V[1001000];
long long book[1001000],siz[1001000],flag[1001000],root[1001000];
void dfs(long long x,long long f,long long r){
	long long i;
	if(book[x] == 1){//如果一个点被搜索到两遍，说明是环
		flag[r] = 2;
		return;
	}
	book[x] = 1;
	siz[r]++;//统计子图大小
	for(i = 0;i < V[x].size();i++){
		if(V[x][i] == f){
			continue;
		}
		dfs(V[x][i],x,r);
	}
}
int main(){
	long long n,m,k,i,a,b,ans = 0,cnt = 0;//ans为连通块的个数，cnt为要删除的边的数量
	cin>>n>>m>>k;
	for(i = 1;i <= m;i++){
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	for(i = 1;i <= n;i++){
		if(book[i] == 0){
        //对每个联通子图进行DFS判断是链还是环，并统计其大小，将它存储到一个点上
			flag[i] = 1;
			root[i] = 1;
			dfs(i,0,i);
		}
	}
	for(i = 1;i <= n;i++){
		if(root[i] == 1){//只有存储了信息的点才计算
			if(siz[i] < k){//小于k直接忽略
				continue;
			}
			if(siz[i] == k){//等于k直接加上
				ans += 1;
				continue;
			}
			ans += siz[i]/k;
			if(flag[i] == 1){//刚刚提到的环和链的不同
				cnt += siz[i]/k;
				if(siz[i] % k == 0){
					cnt--;
				}
			}else{
				cnt += siz[i]/k+1;
				if(siz[i] % k == 0){
					cnt--;
				}
			}
		}
	}
	cout<<ans*k<<" "<<cnt;//记得输出的是大小为k的连通块个数乘以k
}