社区讨论
*这个题可以这么做吗?
P1041[NOIP 2003 提高组] 传染病控制(疑似错题)参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hezjq
- 此快照首次捕获于
- 2025/11/20 04:55 4 个月前
- 此快照最后确认于
- 2025/11/20 04:55 4 个月前
我是用dp[i]表示传染到i 其后续最少感染数 然后有dp[i]=∑dp[j]-max{dp[j]} j∈son[i] dfs
到底层然后递归求dp[1] 然而这个只过了4个点求dalao看看有没有问题或者反例
···cpp
CPP#include<bits/stdc++.h>
using namespace std;
#define MN 350
int n,p,h[MN],tt,h0[MN],dp[MN],tot;
struct lll{
int to,ne;
}a[MN*2];
lll e[MN*2];bool vis[MN];
void link(int x,int y)
{
e[++tt].to=y;e[tt].ne=h0[x];h0[x]=tt;
e[++tt].to=x;e[tt].ne=h0[y];h0[y]=tt;
}
void link2(int x,int y)
{
a[++tot].to=y;a[tot].ne=h[x];h[x]=tot;
}
void Init(int u)
{
int i=h0[u];if(!i) return;
while(i)
{
if(!vis[e[i].to]) link2(u,e[i].to),vis[e[i].to]=1,Init(e[i].to);
i=e[i].ne;
}
return ;
}
void dfs(int u)
{
int sum=0,MM=-1;
int i=h[u]; if(!i) {dp[u]=1;return;}
while(i)
{
dfs(a[i].to);
sum+=dp[a[i].to];
MM=max(MM,dp[a[i].to]);
i=a[i].ne;
}
dp[u]=sum-MM+1;return ;
}
int main()
{
cin>>n>>p;int a_,b_;
for(int i=1;i<=p;i++) cin>>a_>>b_,link(a_,b_);
vis[1]=1;Init(1);
dfs(1);
cout<<dp[1];
cout<<endl; for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...