求解为啥c题不过。。

哭辽

为什么c题过不去

有没有大佬解答一下

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long fat[maxn],val[maxn];
bool flag[maxn];
int n,m;
vector<int> V;
int trace(int num){
	return fat[num]==num?num:trace(fat[num]);
}
void combine(int a,int b){
	int t_a=trace(a),t_b=trace(b);
	if(t_a!=t_b){
		fat[t_a]=t_b;
		val[t_b]+=val[t_a];
		return ;
	}
}
int main(){
	cin>>n>>m;
	memset(fat,0,sizeof(fat));
	memset(val,0,sizeof(val));
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=n;i++) fat[i]=i;
	for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
	for(int i=1;i<=n;i++){
		int a; scanf("%d",&a);
		combine(a,i);
	}
	for(int i=1;i<=n;i++){
		trace(i);
		if(flag[fat[i]]) continue;
		else{
			V.push_back(val[fat[i]]);
			flag[fat[i]]=1;
		}
	}
	sort(V.begin(),V.end());
	int i=V.size();
	long long res=0;
	while(m--){
		res+=V[--i];
		if(i<=0) break;
	}
	cout<<res<<endl;
	return 0;
}
全部评论
第一,vector开long long 第二,并查集查的操作没有路径压缩
点赞 回复 分享
发布于 2019-03-03 01:02
有环不是很好处理。。
点赞 回复 分享
发布于 2019-03-02 15:11
tarjan缩点,从每个无入度点dfs加上累加就好了
点赞 回复 分享
发布于 2019-03-02 15:10

相关推荐

今天 11:12
门头沟学院 Java
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务