社区讨论

萌新泪水旺旺恳求大佬帮忙

P1041[NOIP 2003 提高组] 传染病控制(疑似错题)参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo16far0
此快照首次捕获于
2023/10/22 15:57
2 年前
此快照最后确认于
2023/11/02 15:32
2 年前
查看原帖
额,这个代码为什么会超时和错误呀? 用了 dfn,size 判断子树的方法。
CPP
#include <bits/stdc++.h>//喵内~
#define re register//喵内~
#define int long long
using namespace std;//喵内~
typedef long long ll;
typedef long double ld;
const int N = 305;//喵内~要填数字哟~
inline int read(){
    int s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}//喵内~
int dfn[N],size[N],head[N],cnt;
struct TernaryTree{
	int c[N];
	int lowbit(int x){return x & -x;}
	void add(int x,int y){for (;x<N;x+=lowbit(x))c[x] += y;}
	int query(int x){int res = 0;for (;x>=1;x-=lowbit(x))res += c[x];return res;}
}Tree;
struct node{
	int v,next;
}tree[N << 1];
int ans = 114514,n,m,timer;
int dep[N][N];
void add(int u,int v){
	tree[++cnt].next = head[u];
	tree[cnt].v = v;
	head[u] = cnt;
}
void dfs(int u,int fa,int deep){
	dep[deep][++dep[deep][0]] = u;
	size[u] = 1,dfn[u] = ++timer;
	for (int i = head[u];i;i = tree[i].next){
		int v = tree[i].v;
		if (v == fa)continue;
	    dfs(v,u,deep+1);
	    size[u] += size[v];
	}
}
void bfs(int deep,int sum){
	//if (sum >= ans)
	 //   return;
	if (!dep[deep][0]){
		ans = min(ans,sum);
		return;
	}
	int f = 0;
	for (int i=1;i<=dep[deep][0];i++){
		int v = dep[deep][i];
		if (Tree.query(dfn[v]) - Tree.query(dfn[v] - 1) != 0){
		    f++;
			continue;
		}
		Tree.add(dfn[v],1);Tree.add(dfn[v] + size[v],-1);
		bfs(deep+1,sum + dep[deep][0] - size[v]);
		Tree.add(dfn[v],-1);Tree.add(dfn[v] + size[v],1);
	}
	if (f == dep[deep][0])
	    ans = min(ans,sum);
}
signed main(){
	n = read(),m = read();
	for (int i=1,u,v;i<=m;i++){
		u = read(),v = read();
		add(u,v),add(v,u);
	}
	dfs(1,0,1);
	bfs(2,1);
	printf("%lld\n",ans);
    return 0;
}//喵内~
/*
*/

回复

4 条回复,欢迎继续交流。

正在加载回复...