hack & 请求撤下题解
查看原帖
hack & 请求撤下题解
682735
Qingque楼主2022/9/26 17:20

下面是一组hack数据的生成代码,可以将匈牙利算法的复杂度卡满,在本机上 hack 掉了本题的 倒数第一篇(TLE ,开O2的情况下用时3.6s) 和 倒数第二篇(WA) 题解。

#include<bits/stdc++.h>
using namespace std;
int T=100,n=250;
int main(){
	freopen("hack.in","w",stdout);
	printf("%d\n",T);
	while(T--){
		printf("%d\n",500);
		for(int i=1;i<=n;i++){
			printf("114 F A A\n");
		}
		for(int i=1;i<=n;i++){
			printf("114 M A B\n");
		}
	}
	return 0;
}

其余题解因为常数较小未能 hack 掉,但本题中用匈牙利算法来做二分图匹配的复杂度是 O(Tn3)O(Tn^3). 而数据范围是 T100,n500T \le 100,n\le 500. 所以萌新认为匈牙利算法不应该成为此题的正解。请求管理员将使用匈牙利算法的题解撤下。

2022/9/26 17:20
加载中...