Skip to content

13018: 【原3018】二哥分糖果

题目

题目描述

author: ytytyt13579 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3018

Description

2哥一家有n兄弟,名字分别叫:1哥,2哥... n哥。2哥的幼儿园园长决定给2哥兄弟们发糖果,每个人所得糖果的多少由他们在幼儿园的表现好坏来决定。于是幼儿园找来 m 个幼儿园老师,每个老师提出了自己的意见:“我认为a哥得的糖果应该比b哥多!” 幼儿园园长决定找出一种发糖果的方法,满足各位老师的意见,并且用的糖果最少,每个人最少分到100颗糖果。如果找不出一种方案满足所有老师要求,幼儿园园长就呵呵地吃掉了所有的糖果。

Input Format

第1行2个正整数 n, m,表示2哥一家兄弟数 n 和 老师数 m;

以下 m 行,每行2个整数a, b,表示某个老师认为 a哥的糖果应该比 b哥高。

(注意:不同的老师有可能有同样的想法)

Output Format

若无法找到合法方案,则输出“hehe”(不带引号);否则输出一个数表示最少总糖果数。

Sample Input

2 1
1 2

Sample Output

201

样例解释

有1个老师认为1哥的糖果数应该比2哥多,于是1哥分到了101个糖果,2哥分到了100个糖果,共201个糖果

数据范围

n <= 1000, m <= 2500

yyong119's solution

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX_N 1010
using namespace std;
struct Node {
    int x, candy_assigned;
    Node(int p = 0, int q = 0): x(p), candy_assigned(q) {}
};
int n, m, ans, solved;
vector<int> link[MAX_N];
bool vis[MAX_N];
int in_deg[MAX_N];
queue<Node> q;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read(), m = read();
    for (register int i = 0; i < m; ++i) {
        int x = read(), y = read();
        ++in_deg[x];
        link[y].push_back(x);
    }
    for (register int i = 1; i <= n; ++i)
        if (!in_deg[i]) q.push(Node(i, 100));
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        ans += cur.candy_assigned;
        ++solved;
        for (register int i = 0; i < link[cur.x].size(); ++i)
            if (!(--in_deg[link[cur.x][i]]))
                q.push(Node(link[cur.x][i], cur.candy_assigned + 1));
    }
    if (solved == n) printf("%d", ans);
    else printf("hehe");
    return 0;
}