简报:不能建双向边,只能建单向边。所以为什么呢?(
这题只给了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