下面是一组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). 而数据范围是 T≤100,n≤500. 所以萌新认为匈牙利算法不应该成为此题的正解。请求管理员将使用匈牙利算法的题解撤下。