神奇AC,什么神奇数据
查看原帖
神奇AC,什么神奇数据
417018
dark_moon楼主2022/8/8 17:57

这是AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, w, c[N], d[N], u, v, fa[N], a[N][3], idx, f[N], ans;
int find(int x){
	while(x != fa[x])
	x = fa[x] = fa[fa[x]];
}
pair<int, int> p[N];
int main(){
	scanf("%d%d%d", &n, &m ,&w);
	for(int i = 1; i <= n; i ++)
	fa[i] = i;
	for(int i = 1; i <= n; i ++){
		scanf("%d%d", &c[i], &d[i]);
	}
	for(int i = 1; i <= m; i ++){
		scanf("%d%d", &u, &v);
		fa[find(u)] = find(v);
	}
	for(int i = 1; i <= n; i ++)
	p[i].first = find(i), p[i].second = i;
	sort(p + 1, p + 1 + n);
	p[0].first = 0;
	for(int i = 1; i <= n; i ++){
		if(p[i].first != p[i - 1].first){
			idx ++;
			a[idx][1] += d[p[i].second];
			a[idx][2] += c[p[i].second];
		}
		else{
			a[idx][1] += d[p[i].second];
			a[idx][2] += c[p[i].second];
		}
	}
	n = idx;
//	printf("\n");
//	for(int i = 1; i <= n; i ++)
//	printf("%d %d\n", a[i][1], a[i][2]);
	for(int i = 1; i <= n; i ++){
		for(int j = w; j >= a[i][2]; j --)
		f[j] = max(f[j], f[j - a[i][2]] + a[i][1]);
	}
	for(int i = 1; i <= w; i ++)
	ans = max(ans, f[i]);
	printf("%d", ans);
	return 0;
}
//1 价值   2 价格 

注意看,find函数内并没有

return x;

但最终还是AC,这是什么神奇的数据???

2022/8/8 17:57
加载中...