社区讨论

*这个题可以这么做吗?

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 条回复,欢迎继续交流。

正在加载回复...