#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
class edge{
public:
int to;
edge*next;
edge(int to,edge *next):next(next),to(to){}
};
class node{
public:
int belong,dfn,low,m;
bool vis;//是否在栈里
edge *e;
node():e(nullptr),belong(0),dfn(0),low(0),m(0x7fffffffffffffff),vis(false),pr(false){}
edge *add(int to){return e=new edge(to,e);}
};
unordered_map<int,node> dat;
unordered_map<int,int> rd;
vector<int> sum;
int n,m,u,v,tot,a,b,zero,ans,p,r;
stack<int> st;
void dfs(int x){
dat[x].dfn=dat[x].low=++tot;
st.push(x),dat[x].vis=true;
for(edge*p=dat[x].e;p!=nullptr;p=p->next){
if(!dat[p->to].dfn)
dfs(p->to),dat[x].low=min(dat[x].low,dat[p->to].low);
else if(dat[p->to].vis)
dat[x].low=min(dat[x].low,dat[p->to].dfn);
}
if(dat[x].dfn==dat[x].low){
sum.push_back(0x7fffffffffffffff);
do if(!st.empty()){
dat[st.top()].belong=sum.size();
sum[dat[st.top()].belong]=min(sum[dat[st.top()].belong],dat[st.top()].m);
dat[st.top()].vis=false;
st.pop();
}while(!st.empty()&&st.top()!=x);
}
}
signed main(){
n=read(),p=read();
for(int i=1;i<=p;i++)u=read(),dat[u].m=read();
r=read();
for(int i=1;i<=r;i++)u=read(),v=read(),dat[u].add(v);
for(int i=1;i<=n;i++)if(!dat[i].dfn&&dat[i].m)dfs(i);
//上面为tarjan模板
for(int i=1;i<=n;i++)if(!dat[i].dfn)return printf("NO\n%lld",i),0;
for(int i=1;i<=n;i++)for(edge* p=dat[i].e;p!=nullptr;p=p->next)
if(dat[i].belong!=dat[p->to].belong)rd[dat[p->to].belong]++;
printf("YES\n");
for(int i=1;i<=n;i++)cerr<<dat[i].belong<<' ';
cerr<<endl<<sum.size()<<endl;
for(int i=1;i<=sum.size();i++)cerr<<rd[i]<<' ';
cerr<<endl;
for(int i=1;i<=sum.size();i++)cerr<<sum[i]<<' ';
cerr<<endl;
for(int i=1;i<=sum.size();i++)if(!rd[i])
ans+=sum[i];
printf("%lld",ans);
}
(其中cerr为测试输出,可忽略)
注对于样例一我的代码的测试输出:
1 3 1
3
1 0 0
9223372036854775807 9223372036854775807 0
和第一篇题解对同样内容的输出(屡次wa后对照题解改错,无果。gpt无果):
2 3 1
3
2 0 0
1000000000 10 100