思路

(by tj第1篇，和我的思路一样）

这道题我们先从 i 往 p[i] 各连一条有向边，可以发现一共 n 个点，n 条有向边，且每个点的出入度都为 1。所以不难想到最后这个图会变成若干个环。

然后考虑如何最大化收不到礼物的人数：

对于每一个偶环，假设长度为 k，则只要k/2个人忘带，则都收不到。

对于每一个奇环，则只要 (k+1)/2个人忘带，则都收不到。

所以我们可以用贪心的思想。

对于一个长度为 m 的环，只要 m 个人忘带，则就会有 m 个人收不到礼物。

如果能找到若干个环，使得它们长度之和刚好是 k，那么答案就是k。否则会多牵连一个人，答案则为 k+1。

然后就WA了……

样例没问题

#include<bits/stdc++.h>
using namespace std;
int n,k,p[1000005];
bool vis[1000005]/*统计哪些点已被搜过(在其他环上)*/;
int L[500005]/*环的长度*/,T[1000005]/*长度为i环的个数*/;
int tot;
void search(int u/*环的搜索点*/,int length){
	if(vis[u]==1/*环闭合了*/){
		L[++tot]=length;
		T[length]++;
		return;
	}
	vis[u]=1;
	length++;
	//cout<<u<<" "<<length<<endl;
	search(p[u],length);
}
int LL[500005];bool f[1000005];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		search(i,0);
	}
	/*for(int i=1;i<=tot;i++){
		cout<<L[i]<<" ";
	}*/
	int maxans=0,kk=k;
	for(int i=1;i<=tot;i++){
		if(kk>=L[i]/2){
			kk-=L[i]/2;
			maxans+=(L[i]/2)*2;
		}
		else{
			maxans+=kk*2;
			kk=0; 
			break;
		}
	}
	if(kk)maxans+=kk;
	tot=0;
	for(int i=1;i<=n;i++){
		if(T[i]){
			for(int g=1;T[i];g<<=1){
				T[i]-=max(g,T[i]);
				LL[++tot]=max(g,T[i])*i;
			}
		}
	}
	f[0]=1;
	for(int i=1;i<=tot;i++){
		for(int j=k;j>=LL[i];j--){
			if(f[j-LL[i]])f[j]=1;
		}
	}//dp求出能不能用一些环凑出k
	int minans=k;
	if(!f[k])minans++;
	cout<<minans<<" "<<maxans<<endl;
	return 0;
}