萌新求助

空の軌跡 @ 2019-09-20 20:28:16

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
vector<int>side[1505];
bool vis[1505];
int minn[1505][3];
void dfs(int x)
{
    vis[x]=1;
    minn[x][1]=1;
    int iwan=1999;
    for(int i=0;i<side[x].size();i++)
    {
        int to=side[x][i];
        if(vis[to])continue;
        dfs(to);
        minn[x][1]+=min(minn[to][1],min(minn[to][2],minn[to][0]));
        if(minn[to][1]<=minn[to][0])
        {
            iwan=0;
            minn[x][0]+=minn[to][1];
        }
        else
        {
            minn[x][0]+=minn[to][0];
            iwan=min(iwan,minn[to][1]-minn[to][0]);
        }
        minn[x][2]+=min(minn[to][1],minn[to][0]);
    }
    minn[x][0]+=iwan;
}
signed main()
{
    int n,now,a,b;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>now>>a;
        for(int j=1;j<=a;j++)
        {
            cin>>b;
            side[now].push_back(b);
            side[b].push_back(now);
        }
    }
    dfs(0);
    cout<<min(minn[0][1],minn[0][0]);
}

by shame_djj @ 2019-09-20 20:41:47

q n d m x

by lygmh @ 2019-09-20 20:52:56

@shao_ping 有两种解决方法。 1.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
vector<int>side[1505];
bool vis[1505];
int minn[1505][3];
void dfs(int x)
{
    vis[x]=1;
    minn[x][1]=1;
    int iwan=1999;
    for(int i=0;i<side[x].size();i++)
    {
        int to=side[x][i];
        if(vis[to])continue;
        dfs(to);
        minn[x][1]+=min(minn[to][1],min(minn[to][2],minn[to][0]));
        if(minn[to][1]<=minn[to][0])
        {
            iwan=0;
            minn[x][0]+=minn[to][1];
        }
        else
        {
            minn[x][0]+=minn[to][0];
            iwan=min(iwan,minn[to][1]-minn[to][0]);
        }
        minn[x][2]+=min(minn[to][1],minn[to][0]);
    }
    minn[x][0]+=iwan;
}
signed main()
{
    int n,now,a,b;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>now>>a;
        for(int j=1;j<=a;j++)
        {
            cin>>b;
            side[now].push_back(b);
            //side[b].push_back(now);
        }
    }
    dfs(0);
    cout<<min(minn[0][1],minn[0][0]);
}

2.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
vector<int>side[1505];
bool vis[1505];
int minn[1505][3];
void dfs(int x,int fa)
{
    vis[x]=1;
    minn[x][1]=1;
    int iwan=1999;
    for(int i=0;i<side[x].size();i++)
    {
        int to=side[x][i];
        if(to==fa)continue;
        if(vis[to])continue;
        dfs(to,x);
        minn[x][1]+=min(minn[to][1],min(minn[to][2],minn[to][0]));
        if(minn[to][1]<=minn[to][0])
        {
            iwan=0;
            minn[x][0]+=minn[to][1];
        }
        else
        {
            minn[x][0]+=minn[to][0];
            iwan=min(iwan,minn[to][1]-minn[to][0]);
        }
        minn[x][2]+=min(minn[to][1],minn[to][0]);
    }
    minn[x][0]+=iwan;
}
signed main()
{
    int n,now,a,b;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>now>>a;
        for(int j=1;j<=a;j++)
        {
            cin>>b;
            side[now].push_back(b);
            side[b].push_back(now);
        }
    }
    dfs(0,-1);
    cout<<min(minn[0][1],minn[0][0]);
}

by lygmh @ 2019-09-20 20:53:29

大概是这样，有错再找我。

by 空の軌跡 @ 2019-09-20 21:20:00

@G_M_H

他A不了啊，我代码有什么问题吗

by lygmh @ 2019-09-20 21:30:41

@shao_ping emm懂了，转移方程写错了，这题不是皇宫守卫

by lygmh @ 2019-09-20 21:31:21

我是这样写的

void dfs(int x) {
    dp[x][0]=0;
    dp[x][1]=1;
    for(register int i=0; i<dis[x].size(); i++) {
        dfs(dis[x][i]);
        dp[x][0]+=dp[dis[x][i]][1];
        dp[x][1]+=((dp[dis[x][i]][0]<dp[dis[x][i]][1])? dp[dis[x][i]][0]:dp[dis[x][i]][1]);
    }
}

by 空の軌跡 @ 2019-09-20 21:35:46

@G_M_H

直接说下思路吧

by 空の軌跡 @ 2019-09-20 21:37:27

@G_M_H

这题是所有的边？

by 空の軌跡 @ 2019-09-20 21:38:00

@G_M_H

emm，我好像知道咋回事了

by 空の軌跡 @ 2019-09-20 21:59:16

@G_M_H

A了

thank you