为什么用邻接表记录炸弹能炸的区间会TLE,时间差在哪里了???
#include<bits/stdc++.h>
//#define int long long
//#define int int_128
#define fr front
#define se second
#define fi first
#define mmst0(x) memset(x,0,sizeof(x));
#define mmst1(x) memset(x,1,sizeof(x));
#define mmst3f(x) memset(x,0x3f,sizeof(x));
#define mmstf(x) memset(x,-1,sizeof(x));
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
using namespace std;
typedef long long ll;typedef unsigned long long ull;typedef unsigned short ushort;
typedef pair<int,int> PII;typedef pair<long long,long long> PLL;
char *p1,*p2,buf[100000];int read(){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=x*10+ch-48,ch=nc();}return x*f;}
void prt(int x){if(x<0){putchar('-');x=-x;}if(x>9)prt(x/10);putchar((char)(x%10+'0'));}//int_128输出
//变量区------------------------------------------------------------------------------------------------------------------------------------------------------------
const int inf=0x3f3f3f3f;const double eps=1e-6;const int mod=131;
const int MAXN=(int)1e6+3;const int maxn=(int)1e6+3;const int N=(int)1010;const int M=(int)110;
struct node{
int x,y;
};
node arms[M],bomb[M];//arms->武器,bomb->炸弹
int m,n,k,ans,kx,ky;//m->武器数,n->炸弹数,k->炸弹范围,ans->答案
int f[M][M],q[M],fa[M][M];//f[i][j]->第i炸弹炸武器j时最大能炸到的武器,q[i]->从头炸到i所需最少炸弹数,fa[i][j]
bool check[M][M];//check[i][j]->第i个炸弹能不能炸到第j个武器
bool flag[M];int match[M],h[N],ne[MAXN],e[MAXN],idx;//二分图匹配
//------------------------------------------------------------------------------------------------------------------------------------------------------------------
//函数区 -----------------------------------------------------------------------------------------------------------------------------------------------------------
void add(int x,int y){
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
inline int pf(int x){
return x*x;
}
inline void init(){//初始化与输入
mmst0(check);mmst0(flag);mmst3f(q);memset(h,-1,sizeof(h));
cin>>m>>n>>k;
ans=n;
for(int i=1;i<=m;i++){ cin>>arms[i].x>>arms[i].y; }
for(int j=1;j<=n;j++){ cin>>bomb[j].x>>bomb[j].y; }
cin>>kx>>ky;
return ;
}
inline void check_all(){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(pf(bomb[j].x-arms[i].x)+pf(bomb[j].y-arms[i].y)<=pf(k)){
check[j][i]=1;
}
}
}
return ;
}
inline void check_max(){
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){//倒序是因为先找大的,找到之后再接下去就是继承,可以不用再加个循环
if(check[i][j]==1){
f[i][j]=max(j,f[i][j+1]);
}
}
}
return ;
}
inline void check_min(){
q[m+1]=0;
for(int i=m;i>=1;i--){//因为是倒序递推,所以m+1应该设为0
for(int j=1;j<=n;j++){
if(check[j][i]){
q[i]=min(q[i],q[f[j][i]+1]+1);
}
}
}
return ;
}
inline bool find(int u){//匈牙利算法
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(flag[j]==1){
flag[j]=0;
if(!match[j]||find(match[j])){
match[j]=u;
return true;
}
}
}
return false;
}
inline void dfs(int arms_num,int que){
if(que+q[arms_num]>=ans){
return ;
}
if(arms_num>m){
ans=que;
return ;
}
int record[M];//回溯用的记录数组
for(int i=arms_num;i<=m;i++){
for(int j=1;j<=n;j++){
record[j]=match[j];
if(check[j][arms_num]&&f[j][arms_num]>=i){
add(j,que+1);add(que+1,j);
}
}
mmst1(flag);
if(find(que+1)){
dfs(i+1,que+1);
}
for(int j=1;j<=n;j++){
match[j]=record[j];
}
mmst0(ne);mmst0(e);memset(h,-1,sizeof(h));idx=0;
}
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------
signed main(){
ios::sync_with_stdio(false);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
init();//初始化
check_all();//判断能不能炸到
check_max();//最大能炸到的武器
check_min();//从这炸到那所需最少炸弹数
dfs(1,0);
cout<<ans;
return 0;
}