回复 @真呆菌 :
恶心

有的事，必须澄清

状态压缩类动归，难度中等

回复 @HouJikan :
这个显然不对把……
比如这4个点用两个矩形覆盖：
(1,0)、(2,100)、(3,1)、(4,101)
显然最小答案是4。但是你的算法会得出200……

公牛和母牛[尼尔湖，2008]
农夫约翰想要排列 N只（1<= N<= 100,000），奶牛和公牛
在单独一行中将出席这一年一度的展览会。
FJ观察到，近期公牛已经相当好斗;
如果两个公牛靠得太近_，他们会吵架，
开始战斗，破坏了和平。以往足智多谋，巧
计算任何两个公牛必须至少有K（0<= K<N）
为了避免打击他们的奶牛。
FJ想请你帮他通过计算可能的数
Ñ​​公牛和母牛避免任何战斗序列。 FJ认为
所有公牛的是相同的，所有奶牛是相同的;因此，这两个序列是唯一的，如果他们有不同种类的牛不同
在一些位置上。
问题名称：bullcow
输入格式：
*第1行：两个用空格隔开的整数：N和K
样例输入（bullcow.in）：
42
输入说明：
FJ想要一排4牛，但任何两个公牛必须至少有
两头牛在他们之间。
输出格式：
*第1行：代表的方法的数量FJ可以一个整数
牛创造这样一个顺序。因为这个数字可以是
相当大，将结果输出模5000011。
样本输出（bullcow.out）：
6
输出说明：
以下是六种可能的序列FJ可以创建（请注意，“C”代表母牛和'B'代表公牛）：
CCCC
BCCC
CBCC
CCBC
CCCB
BCCB

回复 @lqwang1985 :
题目说，质因子

水题还★☆，好坑啊

水题没有一遍AC，我有愧于人民啊！

带“到根边权和”的并查集，解法真漂亮！

@digital-T 应该是有了STL后整个人都变懒了。

回复 @天一阁 :
你不觉得这个毛团萌萌哒么……

sort函数的cmp必须是全局函数或者static……也就是不能在不同的对象中让cmp有不同语义，杯具了一中午……

为何粘上这个图！！！

为什么图折磨恶心！

文件名的最后竟然是1，一直以为是l

回复 @省选完挂，OI再见 : 贴代码很不美观啊

单调队列不是O（n）吗QAQ

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 205
int map[N][N];
int n, m;
inline void floyd(){
for (int i = 1; i <= n; i ++) map[i][i] = 0;
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++){
if (i != k){
for (int j = 1; j <= n; j ++)
if (j !=i && j != k){
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
int main(){
freopen("hardest.in", "r", stdin);
freopen("hardest.out", "w", stdout);
int T;
scanf("%d", &T);
while (T --){
memset(map, 0x3f, sizeof(map));
scanf("%d %d", &n, &m);
int x, y, z;
for (int i = 1; i <= m; i ++){
scanf("%d %d %d", &x, &y, &z);
map[x][y] = min(map[x][y], z);
map[y][x] = min(map[x][y], z);
}
floyd();
if (map[1][n] != 0x3f3f3f3f)
printf("%d\n", map[1][n]);
else printf("-1\n");
}
return 0;
}

注意longlong啊！！

请问管理员题目上传的时候测试文件怎么上传？@cstdio