不是标签图遍历问题吗?怎么变成线性代数问题?
查看原帖
不是标签图遍历问题吗?怎么变成线性代数问题?
1314340
maimaimai楼主2024/7/27 12:02

高斯消元ax+bx=y,a和b是可以任意,题目刚好是做特例,a和b都是1。

观察

[v1+v2]-[v2+v3]+[v3+v4]=[v1-v4]

[v1+v2]-[v2+v3]+[v3+v4]-[v4+v5]=[v1+v5]

基数数量路径[Va−Vb][V_a-V_b],偶数数量路径或者题目提供[Va+Vb][V_a+V_b]

只要存在[Va−Vb][V_a-V_b]和[Va+Vb][V_a+V_b],就秒解出来一个,能快速求出一个块里所有数据。

后续可能有几个块,只要块里没有[Va−Vb][V_a-V_b]和[Va+Vb][V_a+V_b]对出现就接近没解。(当然还有点细节我不去再细细考虑,毕竟实践检验真理,原因最下面)

优化:排序以下每个点的度,贪心一下,

1.毕竟这个最多度都点,连没2条对应路径(渣渣),最好找都没找到,当然不等于这个块是没解(只是大概率无解)

2.求出一个解,这个度最多,整个块求出来也是最快。

PS:我去写代码是不可能的XD,毕竟我也不参与OI比赛,找深度图遍历的题给学生联系,感觉这题不合适。顺带看看标签?!不是说好图遍历吗?

2024/7/27 12:02
加载中...