求解惑
查看原帖
求解惑
536128
Liao_luo楼主2022/6/18 23:10

为什么用邻接表记录炸弹能炸的区间会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;
}
2022/6/18 23:10
加载中...