3
14
2015
0

Codeforces Round #203 (Div. 2)

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!

           

Category: codeforces | Tags: | Read Count: 557

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com