我的AC代码:
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long u,v;
}a[20005];
long long dfn[20005],w[20005],in[20005],sum,cnt,c[20005],e[20005],mx[20005],d[20005],f[20005];
vector<int> vx[20005],ex[20005];
stack<int> s;
void tarjan(long long u)
{
s.push(u);
f[u] = 1;
dfn[u] = ++cnt;
w[u] = cnt;
for(long long i = 0;i < vx[u].size();i++)
{
long long nt = vx[u][i];
if(dfn[nt] == 0)
{
tarjan(nt);
w[u] = min(w[u],w[nt]);
}
else if(f[nt] != 0)
{
w[u] = min(w[u],dfn[nt]);
}
}
if(dfn[u] == w[u])
{
sum++;
f[u] = 0;
c[u] = sum;
e[sum] = mx[u];
d[sum] = u;
while(s.top() != u)
{
long long cur = s.top();
s.pop();
f[cur] = 0;
c[cur] = sum;
e[sum] = min(e[sum],mx[cur]);
d[sum] = min(d[sum],cur);
}
s.pop();
}
return;
}
void mark(long long cur)
{
if(cur == 0)
{
return;
}
f[cur] = 1;
for(long long nxt : ex[cur])
{
mark(nxt);
}
return;
}
int main()
{
long long n,p,m,z = 0,ans = 0;
memset(mx,0x3f,sizeof(mx));
scanf("%lld%lld",&n,&p);
for(long long i = 1;i <= p;i++)
{
long long x,y;
scanf("%lld%lld",&y,&x);
mx[y] = x;
}
scanf("%lld",&m);
for(long long i = 1;i <= m;i++)
{
long long x,y;
scanf("%lld%lld",&x,&y);
a[i] = {x,y};
vx[x].push_back(y);
}
cnt = 0;
for(long long i = 1;i <= n;i++)
{
if(dfn[i] == 0)
{
tarjan(i);
}
}
for(long long i = 1;i <= m;i++)
{
long long p = c[a[i].u],q = c[a[i].v];
if(p != q)
{
in[q]++;
ex[p].push_back(q);
}
}
for(long long i = 1;i <= sum;i++)
{
if(in[i] == 0)
{
if(e[i] == 0x3f3f3f3f3f3f3f3f)
{
z = n + 1;
}
else
{
ans = ans + e[i];
mark(i);
}
}
}
if(z == 0)
{
printf("YES\n%lld",ans);
return 0;
}
printf("NO\n");
for(long long i = 1;i <= n;i++)
{
if(mx[i] == 0x3f3f3f3f3f3f3f3f)
{
z = min(z,d[c[i]]);
}
}
printf("%lld\n",z);
return 0;
}
在样例二中输出的是2,但提交却能AC,数据太水!