警示后人&&玄关求问
查看原帖
警示后人&&玄关求问
1153677
Treap_Kongzs楼主2025/1/21 00:06

简报:不能建双向边,只能建单向边。所以为什么呢?(

详情:

这题只给了n个点权,我们要自己处理边权然后跑MST(你就说最大生成树缩写是不是MST吧),但是建边时,如果用

for(long long i=1;i<=n;i++)
	{
		for(long long j=1;j<=n;j++)
		{
			if(x[i]!=x[j])
			{

这样显然是建的双向边,然而就会出玄学错误,有人vector建图爆空间我的MST专属链式前向星WA到只有样例分10pts,要这么建边:

    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        for(int j=1;j<=i;j++)
        {
            if(i==j)continue;
            adde(i,j,w[i]^w[j]);
        }
    }

小 main 包中建边部分 j 层循环的 n 改成 i,即建单向边。

然而为什么双向边不行呢?玄关求问洛谷的各位大佬们,谢谢。

数据支持:

我觉得可能是双向边会导致错误地选取边,但是不知道为什么。

在 USACO 官网上下了 #2 来看。

正确的程序会选取这些边:

15 2
20 17
17 14
7 3
4 3
10 8
12 9
20 13
19 5
11 3
15 1
10 9
19 2
8 3
17 16
18 6
11 1
20 6
6 3

而我的 WA 程序就会选这些边:

15 2
20 17
17 14
7 3
4 3
10 8
12 9
20 13
19 5
11 3
15 1
10 9
6 8
6 11
6 13
6 15
6 16
6 19
6 18

#2:

input:

20
535558611
528635334
396080579
732066706
467386290
1004729279
735228602
803937259
802928267
332544747
730232054
334491791
867053722
263176102
603420870
196589974
870463126
67075811
670701723
260477058

output:

18409649596
2025/1/21 00:06
加载中...