0分求hack
查看原帖
0分求hack
1073879
Karl_Wan楼主2024/12/1 14:51

哪位dalao能提供一下hack数据或者指出我的方法错在哪里了吗?谢谢!

我的思路是:把所有外围的白色节点全部去掉,最终剩下一棵根节点和叶子节点都是黑色的树,里面余下的白色节点数量就是答案

评测记录

代码:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int blk[100005],n,ans;
vector<int> G[100005];
queue<int> q;
void bfs()
{
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        //cout<<now<<endl;
        int i,j; 
        //erase太麻烦,-1为标记删除 
        for(i=0;i<G[now].size()&&G[now][i]==(-1);i++){}
        if(G[G[now][i]].size()==2&&!blk[G[now][i]])//会不会产生新的叶子结点 
        {
            q.push(G[now][i]);//如果会,就加进队列 
        }
        //在当前节点的父节点的边集里找到当前节点并删除 
        for(j=0;j<G[G[now][i]].size()&&G[G[now][i]][j]!=(G[now][i]);j++){}
        G[G[now][i]][j]=(-1);
        ans--; 
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>blk[i];
        if(!blk[i]) ans++;
    }
    for(int i=1;i<n;i++)
    {
        int x,y;cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(G[i].size()==1&&!blk[i])
        {
            q.push(i);
        }
    }
    bfs();
    cout<<ans;
    
    return 0;
}
2024/12/1 14:51
加载中...