调试时发现奇怪错误,具体见注释。请大佬帮忙看一下,谢谢。
#include<bits/stdc++.h>
using namespace std;
int n;
int p;
int r;
int a[3005],money[3005],t[3005];
vector<int> edge[3005];
vector<int> temp[3005];
int tong[3005][3005];
int cnt,scc[3005],low[3005],num[3005];//tarjian的数组
int mn[3005],ansmn[3005];//编号最小 ,贿赂钱数最小
int tot;//强联通个数
stack<int> dot;//栈
int u[3005],v[3005];//输入的点
int get[3005],flag[3005];//get 表示入度,flag 表示是否可以直接贿赂
long long ans=0;
void tarjan(int x){
cnt++;
num[x]=low[x]=cnt;
dot.push(x);
for(int i=0;i<edge[x].size();i++){
int y=edge[x][i];
if(!num[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
if(!scc[y])low[x]=min(low[x],num[y]);
}
if(low[x]==num[x]){
tot++;
int y=0;
while(y!=x){
y=dot.top();
dot.pop();
scc[y]=tot;
mn[tot]=min(mn[tot],y);
ansmn[tot]=min(ansmn[tot],t[y]);
}
}
}
void dfs(int x,int ok){
if(ok==1)flag[x]=ok;
for(int i=0;i<temp[x].size();i++){
int v=temp[x][i];
dfs(v,max(flag[v],ok));
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)mn[i]=INT_MAX/3,t[i]=INT_MAX/3,ansmn[i]=INT_MAX/3;
scanf("%d",&p);
for(int i=1;i<=p;i++)scanf("%d%d",&a[i],&money[i]),t[a[i]]=money[i];
scanf("%d",&r);
int sum=0;
for(int i=1;i<=r;i++){
int t=get[1];
scanf("%d%d",&u[i],&v[i]);
if(get[1]!=t)sum+=get[1]-t;
edge[u[i]].push_back(v[i]);
}
cout<<sum<<endl;//这个错误太奇怪了,调试的时候发生的问题,理论上sum应该是0啊,但是有数据使它大于0
for(int i=1;i<=n;i++){
if(!scc[i]){
tarjan(i);
}
}
for(int i=1;i<=p;i++){
flag[scc[a[i]]]=1;//可以直接贿赂
}
for(int i=1;i<=r;i++){
if(tong[scc[u[i]]][scc[v[i]]])continue;
if(scc[u[i]]==scc[v[i]]){
continue;
}
tong[scc[u[i]]][scc[v[i]]]=1;
get[scc[v[i]]]++;temp[scc[u[i]]].push_back(scc[v[i]]);
}
bool tag=1;
for(int i=1;i<=tot;i++){
if(get[i]==0&&flag[i]==0){//不可以贿赂且入度为零
tag=0;//无法联通
}
if(get[i]==0){
ans+=ansmn[i];//累计最小贿赂的财物
}
}
if(tag){
cout<<"YES\n";
cout<<ans;
}
else{
ans=INT_MAX;
for(int i=1;i<=tot;i++){
if(get[i]==0)dfs(i,flag[i]);
}
for(int i=1;i<=tot;i++){
if(flag[i]==0)ans=min(ans,(long long)mn[i]);
}
cout<<"NO\n";
cout<<ans;
}
return 0;
}