不知道为什么错了,样例也过不了
CODE:
#include<bits/stdc++.h>
using namespace std;
const int maxn=3005,inf=1e9+7;
int n,p,r;
int cost[maxn];
vector<int> E[maxn];
int dfn[maxn],low[maxn],stk[maxn],num,top,co[maxn],col,val[maxn],ind[maxn];
void tarjan(int u){
dfn[u]=low[u]=++num;
stk[++top]=u;
for(auto v:E[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(!co[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
co[u]=++col;
val[col]=inf;
if(cost[u]!=0)val[col]=cost[u];
while(stk[top]!=u){
co[stk[top]]=u;
if(cost[stk[top]]!=0)val[col]=min(val[col],cost[stk[top]]);//存每个强连通分量中的最小金额
top--;
}
top--;
}
}
vector<int> nw[maxn]; //新图
bool vis[maxn];//指不能被贿赂的强连通分量
int ans1,ans2=inf;
void dfs(int u,int fa){
for(auto v:nw[u]){
if(v==fa)continue;
if(cost[v]==0){//不能贿赂
vis[v]=1;
dfs(v,u);
}else{
return;
}
}
}
int main(){
cin>>n>>p;
for(int i=0;i<p;i++){
int x,y;
cin>>x>>y;
cost[x]=y;
}
cin>>r;
for(int i=0;i<r;i++){
int u,v;
cin>>u>>v;
E[u].push_back(v);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++){
for(auto v:E[u]){
if(co[u]!=co[v]){
nw[co[u]].push_back(co[v]);
ind[co[v]]++;
}
}
}
bool flag=0;
for(int i=1;i<=col;i++){
if(!flag&&ind[i]==0&&cost[i]){//可以贿赂
ans1+=cost[i];
continue;
}
flag=1;//已经存在不可贿赂的点
vis[i]=1;
dfs(i,0);
}
if(!flag){
cout<<"YES\n"<<ans1<<'\n';
return 0;
}
for(int i=1;i<=col;i++){
if(!vis[i])continue;
for(int j=1;j<=n;j++){
if(co[j]==i){
ans2=min(ans2,j);
}
}
}
cout<<"NO\n"<<ans2<<'\n';
return 0;
}
玄关