多比特杯武汉工程大学第六届ACM新生赛（同步赛）D薇尔莉特能拿多少棵碧根果(拓扑)

题目

给出n个点和m条有向边

原图中的边u->v，我们建立方向图即v->u

其中u的入度++

在一个拓扑图中我们可以容易的判定是否存在一个圆，即圆中的值可以任意取

我们把入读为0的边放入队列中，因为是反向图

我们需要把该点的权值赋给该点指向的目标点

由于目标点只能从众多指向他的点选一个来加，所以我们要维护一个指向他的点的权值的最大值

然后做一遍拓扑，如果有点没有经过就说明以该点为起点可以进入一个环中，这是最大值是1e8

其他情况直接遍历找最大值就行了

#define int long long//__int128 2^127-1(GCC)
#define PII pair
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
vector<int>q[N];//边
int a[N];//每个点权值
int in[N];//入度
bool st[N];//是否被经过
int son[N];//指向该点的所以点中的权值最大值
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int maxx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxx = max(maxx, a[i]);
    }
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        q[v].push_back(u);
        in[u]++;
    }
    queue<int>que;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            que.push(i);
        }
    }
    while (que.size()) {
        int t = que.front();
        st[t] = 1;
        que.pop();
        for (auto w : q[t]) {
            son[w] = max(a[t], son[w]);
            in[w]--;
            if (in[w] == 0) {
                a[w] = min((int)1e8, a[w] + son[w]);
                maxx = max(maxx, a[w]);
                que.push(w);
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (st[i] == 0) {
            cnt++;
        }
    }
    if (cnt) {
        maxx = (int)1e8;
        for (int i = 1; i <= n; i++) {
            if (a[i] == maxx) {
                cnt++;
            }
        }
    }
    else {
        for (int i = 1; i <= n; i++) {
            if (a[i] == maxx) {
                cnt++;
            }
        }
    }
    cout << cnt << "\n";
    cout << maxx << "\n";
}