46分求助,发现奇怪错误
  • 板块P1262 间谍网络
  • 楼主Maxmei
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/5/31 22:00
  • 上次更新2023/10/23 14:12:15
查看原帖
46分求助,发现奇怪错误
231740
Maxmei楼主2023/5/31 22:00

调试时发现奇怪错误,具体见注释。请大佬帮忙看一下,谢谢。

#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;
}
2023/5/31 22:00
加载中...