社区讨论
萌新泪水旺旺恳求大佬帮忙
P1041[NOIP 2003 提高组] 传染病控制(疑似错题)参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo16far0
- 此快照首次捕获于
- 2023/10/22 15:57 2 年前
- 此快照最后确认于
- 2023/11/02 15:32 2 年前
额,这个代码为什么会超时和错误呀?
用了
CPPdfn,size 判断子树的方法。#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 条回复,欢迎继续交流。
正在加载回复...