缩点时在新节点中保存最小花费和最小编号即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
using namespace std;
const int N=3050,INF=1<<25;
int n,m,w[N];
int sz[N],val[N],idx[N],cnt=0,d[N];
int dfn[N],low[N],num=0,inq[N];
int ans=0,id=INF;
vector<int> e[N];
stack<int> S;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void tarjan(int o)
{
dfn[o]=low[o]=++num;
inq[o]=1,S.push(o);
for(int i=0;i<e[o].size();i++)
{
int to=e[o][i];
if (!dfn[to])
{
tarjan(to);
low[o]=min(low[o],low[to]);
}
else if (inq[to])
low[o]=min(low[o],dfn[to]);
}
if (dfn[o]==low[o])
{
int x;++cnt;
do{
x=S.top();
inq[x]=0,S.pop();
idx[x]=cnt;
val[cnt]=min(val[cnt],w[x]);
sz[cnt]=min(sz[cnt],x);
} while (x!=o);
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
w[i]=sz[i]=val[i]=INF;
int T=read();
while (T--)
{
int x=read();
w[x]=read();
}
m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
e[u].push_back(v);
}
for(int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
for(int j=0;j<e[i].size();j++)
{
int u=i,v=e[i][j];
if (idx[u]!=idx[v]) d[idx[v]]++;
}
for(int i=1;i<=cnt;i++)
if (!d[i])
{
if (val[i]==INF)
id=min(id,sz[i]);
else
ans+=val[i];
}
if (id==INF)
printf("YES\n%d",ans);
else
printf("NO\n%d",id);
return 0;
}