这个题在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就是上面构造的那个数据。那么感觉这题的数据应该是没有问题了。如有问题请联系我。

• 相关文章
• 全局相关文章