vector pushback阶段RE70pts求助
查看原帖
vector pushback阶段RE70pts求助
881015
Resstifnurvˆwˆ.tar.gz楼主2023/11/11 11:28
#include<iostream>
#include<vector>
#include<cstring>

inline int read(){
	int ret=0;
	char ch=' ',c=getchar();
	while(!('0'<=c&&c<='9')) ch=c,c=getchar();
	while('0'<=c&&c<='9') ret=((ret<<1)+(ret<<3)+(c^48)),c=getchar();
	return ret=='-'?-ret:ret;
}
inline int min(int x,int y){ return x<y?x:y; }

int n,m;
const int N=300+10,M=600+10;

int to[M],nt[M],idx,h[N];
inline void add(int x,int y){
	to[idx]=y;
	nt[idx]=h[x];
	h[x]=idx++;
}

std::vector<int> level[N];
int sz[N];
void dfs_level(int u,int fa,int lv){
	sz[u]=1;
	for(int i=h[u];i!=-1;i=nt[i]){
		int j=to[i];
		if(j==fa) continue;
		level[lv].push_back(i);
		dfs_level(j,u,lv+1);
		sz[u]+=sz[j];
	}
}

bool cut[M];
void dfs_cut(int u,int fa,bool op){
	for(int i=h[u];i!=-1;i=nt[i]){
		int j=to[i];
		if(j==fa) continue;
		cut[i]=op;
		dfs_cut(j,u,op);
	}
}

int ans=0x3f3f3f3f;
void dfs_ans(int lv,int num){
	ans=min(ans,num);
	for(int i=0;i<(int)level[lv].size();i++){
		int id=level[lv][i];
		if(cut[id]) continue;
		cut[id]=true;
		dfs_cut(to[id],to[id^1],true);
		dfs_ans(lv+1,num-sz[to[id]]);
		cut[id]=false;
		dfs_cut(to[id],to[id^1],false);
	}
}

int main(){
	memset(h,-1,sizeof(h));
	n=read(),m=read();
	int x,y;
	while(m--){
		x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	dfs_level(1,-1,1);
	dfs_ans(1,n);
	printf("%d",ans);
	return 0;
}

排查发现问题发生在 void dfs_level() 处, 但是找不到原因,RE报错显示 Aborted/IOT trap.

悬关sto orz

2023/11/11 11:28
加载中...