CF 240E, 一些意外状况.
这个题在Codeforces上是比较弱的……所以在CF上AC不一定是对的……
我现在在造这个题的数据……然后用了一些奇怪的方法gen数据……
然后发现某种姿势下我的朱刘/Edmonds会MLE……
然后为了获得正确的out在CF上拉了几段AC代码然后跑出了不同的out……
我造了一个比较小的数据是这样的：
1000 3983 1 2 1 2 3 1 3 4 1 4 5 1 ...... 997 998 1 998 999 1 999 1000 1 4 1 0 5 2 0 6 3 0 ...... 997 994 0 998 995 0 999 996 0 1000 997 0 7 1 0 8 2 0 9 3 0 10 4 0 ...... 998 992 0 999 993 0 1000 994 0 8 1 0 9 2 0 10 3 0 ...... 997 990 0 998 991 0 999 992 0 1000 993 0
它是用这段程序生成的：
// Author: Ruchiose
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define i64 long long
#define d64 long double
#define fortodo(i, f, t) for (i = f; i <= t; i++)
using namespace std;
int main()
{
int N = 1000;
printf("%d %d\n", N, N * 4 - 17);
int i;
fortodo(i, 1, N - 1) printf("%d %d 1\n", i, i + 1);
fortodo(i, 1, N - 3) printf("%d %d 0\n", i + 3, i);
fortodo(i, 1, N - 6) printf("%d %d 0\n", i + 6, i);
fortodo(i, 1, N - 7) printf("%d %d 0\n", i + 7, i);
}
显然，为了从1到达i必须要先到达i-1，因此后3N-16条边都是没用的，答案应该是修复所有需要修复的边。
下面是拉来的一些AC代码的输出：
-1
3 997 998 999
-1
999 629 2514 2515 2516 2517 2518 2519 2520 25......
-1
999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......
999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......
（似乎-1会被代码高亮君吃掉囧）
看起来只有jiry_2和sone的程序可以跑出正常的结果。
可是这两个程序里面M开了200万，而这样的数据似乎会让空间开销到N^2级别……
然后N取5000的时候这两个程序已经输出-1了。
然后我已经找不到可以确定是正确的程序了……
（杜教：你可以去学习一下O(MlogN)的写法）
所以这个姿势的数据就只能放到N=1000……感到非常囧。
关于这两个程序在其它姿势gen的数据里是否和我的程序一样还没有测试……因为spj还没写……
多半最后是拿这三个程序的众数造out了囧。
UPD:
数据&SPJ已造。我的7915842造出的数据，sone的7184472和jiry的8162109都AC了（tsinsen: 978615&978616）。
大概是随机数据很弱的原因，Stilwell的5485603和vfk的2406412通过了除了#12以外的所有测试点（tsinsen: 978619&978623）。
其中#12就是上面构造的那个数据。那么感觉这题的数据应该是没有问题了。如有问题请联系我。
评论 (0)
