A不说了
B.奇怪的题目，奇怪的输入，奇怪的爆搜。
C.有n个点（x[i],y[i]），要求用最小的直线行走次数到达每个点并回到原点。（每次都得回一次原点。）n<=10W
题解：按绝对值排序模拟即可。
官方题解：http://codeforces.com/blog/entry/9042
E.给出一个错误的floyed算法，
for (i = 1; i <= k; i++) {
v = a[i];
for(j = 1; j <= n; j++)
for(r = 1; r <= n; r++)
ans[j][r] = min(ans[j][r], ans[j][v] + ans[v][r]);
}
给出n，m以及a数组，求m条边使得这个floyed运算结果错误。
题解：构造题 Orz 首先这个错误的算法其实是只以a数组里的点作为中间节点的最短路径，所以我们只要构造一条无论如何都要经过未标记点的最短路即可。
我想了一种构造方法：选两个a[1],a[2]，再选个没被标记的点t。连边t-a[1],t-a[2]。然后构造其他边，保证不会有a[i]连边a[i]-a[1],a[i]-a[2]。
这样最短路其实是2，而该算法结果比2大
一交WA了
Checker Log wrong answer Graph must be connected
于是去膜拜zhj的代码。发现也可以先找一个t，然后让t向所有点连边。然后再补全其他边的时候直接不连a[1],其他就可以随便连了。Orz！
评论 (0)
