求助! 93pts WA 4#
查看原帖
求助! 93pts WA 4#
817044
cjwdyzxfblzs楼主2023/3/22 18:52

不知道是哪里出了问题 俺的评测记录,真的很离谱欸

#include <bits/stdc++.h>

using namespace std;

#define int unsigned long long

const int N = 100010;

int h[N], e[N], ne[N], idx;
int id[N], scc_cnt, sizes[N];
int stk[N], top;
int dfn[N], low[N], timestamp;
bool in_stk[N];
int n, p, r;
int money[N]; bool st[N];
int dout[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], low[j]);
    }
    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt ++ ;
        do
        {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sizes[scc_cnt] = min(sizes[scc_cnt], money[y]);
        } while (y != u);
    }
}

signed main()
{
    memset(h, -1, sizeof(h));
    memset(sizes, 0x3f, sizeof(sizes));
    memset(money, 0x3f, sizeof(money));

    cin >> n; cin >> p;
    for (int i = 1; i <= p; i ++ ) 
    {
        int x;
        cin >> x;
        st[x] = true;
        cin >> money[x];
    }
    cin >> r;
    for (int i = 1; i <= r; i ++ ) 
    {
        int u, v;
        cin >> u >> v;
        if (st[u] && !st[v])
        {
            p ++ ;
            st[v] = true;
        }
        add(u, v);
    }

    
    if (p < n) 
    {
        cout << "NO" << endl;
        for (int i = 1; i <= n; i ++ )
            if (!st[i])
            {
                cout << i << endl;
                exit(0);
            }
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i] && money[i] != 0x3f3f3f3f)
            tarjan(i);
    // cout << "No problem" << endl;

    // for (int i = 1; i <= n; i ++ )
    // {
    //     if (!dfn[i])
    //     {
    //         cout << "NO" << endl;
    //         cout << i << endl;
    //         return 0;
    //     }
    // }

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int v = e[j];
            if (id[i] != id[v])
                dout[id[v]] ++ ;
        }
    
    // cout << "NO problem" << endl;

    int ans = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i])  ans += sizes[i];
    
    cout << "YES" << endl;
    cout << ans << endl;
    
    return 0;
}
// @sjzez__chess
2023/3/22 18:52
加载中...