近几天的悲剧合集

首先，前天晚上鼓起勇气写fhq的K凹凸序列，写来写去，它竟然给我超时。好伤心的。后来，猛然间，发现我的左偏树的combine是这么写的：

int combine (int i, int j)
{if (key[j] > key[i])swap (&i, &j);if (!j) return i;rc[i] = combine (rc[i], j);if (dist[rc[i]] > dist[lc[j]])swap (&lc[i], &lc[j]);dist[i] = dist[rc[i]] + 1;return i;
}





这还是左偏树吗？根本就不交换左右子树。。于是，被我一改，改成



int combine (int i, int j)
{if (key[j] > key[i])swap (&i, &j);if (!j) return i;rc[i] = combine (rc[i], j);if (dist[lc[i]] > dist[lc[j]])swap (&lc[i], &lc[j]);dist[i] = dist[rc[i]] + 1;return i;
}





一测，还是超了。发现，这次交换的是i的左孩子和j的左孩子，有用吗？

于是，又变成这副模样：


int combine (int i, int j)
{if (key[j] > key[i])swap (&i, &j);if (!j) return i;rc[i] = combine (rc[i], j);if (dist[lc[i]] > dist[rc[i]])swap (&lc[i], &rc[i]);dist[i] = dist[rc[i]] + 1;return i;
}


这样总可以了吧。。可是，还是超了。我看xqz写的都是斜堆，怎么比我的还快些呢？某一次，我把带//的两句删了，发现竟然过了。。好神奇，斜堆比左偏树快。。。

猛然之间，发现我写的竟然变成了右偏树。。。怎么会这样。。。于是，最终版本如下，终于过了：




int combine (int i, int j)
{if (key[j] > key[i])swap (&i, &j);if (!j) return i;rc[i] = combine (rc[i], j);if (dist[lc[i]] < dist[rc[i]])swap (&lc[i], &rc[i]);dist[i] = dist[rc[i]] + 1;return i;
}


昨天用ld的最大流的方法写省队集训day1的snake，写来写去最后就是错那么一个点。。好悲伤。。我静态查错查了好久，硬是没发现什么错误。我想，可能是增广不够吧，于是我在求了最大流之后随手又加了一句isap()，发现竟然过了！！好开心！！但到底是错在那个地方呢？我很怀疑是我的gap。把gap优化删了之后就过了，泪流满面。。

以后请注意，gap优化应该写成这个样子：

      else{--gap[dtmp = dist[i]]; /* DO NOT FORGET */e = adm[i] = edge[i];for (mindist = vexsize - 1; e; e = g[e].n)if (dist[g[e].t] < mindist && g[e].c)mindist = dist[g[e].t];++gap[dist[i] = mindist + 1];if (!gap[dtmp]) break; /* DO NOT FORGET */if (i != src) i = pred[i];}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！