商汤的AI伴游小精灵

Table of Contents

输入格式
输出格式
数据规模
- 样例输入复制
- 样例输出复制

北京市商汤科技开发有限公司面向青少年研发了一款智能伴游机器人– AI 伴游小精灵。一经推出，深受孩子们的喜爱，可爱又机智的小精灵会想出很多有趣的小游戏来启迪孩子们思考。今天，小精灵给你提出了一个神奇又有趣的多米诺骨牌小游戏。

你手上有一副神奇的多米诺骨牌，数量有 nn个，编号为 1 sim n1∼n。它们之间存在着 n-1n−1 个单向推倒关系，即推倒 xx 会导致 yy 也被推倒，而且这样的关系都满足 x<yx<y，且每组关系中的 yy 不会重复。

一开始只有 11 号骨牌不会被其他骨牌推倒，所以你只需要推倒 11 号骨牌就可以推倒所有的骨牌。

小精灵给你提的问题是：如果我们允许去掉 22个骨牌，那么在最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下？

输入格式

第一行输入一个整数 nn，表示有 nn 个多米诺骨牌。

接下来有 n-1n−1 行的输入，每行输入两个整数 x,yx,y，表示推倒 xx 会导致 yy 也被推倒。

输出格式

输出一个整数表示去掉两个骨牌之后，最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下。

数据规模

n le 5 imes 10^3n≤5×103

样例输入复制

样例输出复制

题解：注意点可能存在连续推倒的情况

我的测试数据

input
6
1 2
1 3
2 4
3 5
4 6

out
3

注意题目中提及的单方向推倒

存在问题的代码：(但是能ac

#include <iostream>
#include <algorithm>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
typedef struct{
    int place;
    int cnt;
}node;
node a[5050];
int t[5050][5050];
bool cmp(node a, node b){
    return a.cnt > b.cnt;
}
int main(){
    ll n, y, x;
    sl(n);
    REP(i, 1, n+2){
        a[i].place = i;
    }
    REP(i, 1, n){
        cin >> x >> y;
        t[x][y] = 1; // 即x可以推y
        a[x].cnt++;  // 节点个数
    }

    sort(a+1, a+n, cmp);

    int ans = a[1].cnt + a[2].cnt; // 未排除连续推倒情况
    //cout << ans << '
';
    if(a[1].place == 1 || a[2].place == 1)
        ans--;
    if(t[a[1].place][a[2].place]){
        //如果是1就可以推倒
        ans--;
    }
     cout << ans + 1<< endl;
}