不知道是哪里出了问题 俺的评测记录,真的很离谱欸
#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