求助,TLE#8
  • 板块P1262 间谍网络
  • 楼主wangft
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/24 22:08
  • 上次更新2025/7/25 11:31:41
查看原帖
求助,TLE#8
1068071
wangft楼主2025/7/24 22:08
#include<bits/stdc++.h>
using namespace std;
int n,w[6030],r,id,v[3030],kuai[3030],s[3030],vis[3030],ans,v1[3030];
vector<int>a[6030];
void dfs(int p,int k){
	int i,j;
	if(v[p]==1){
		if(kuai[p]==0) kuai[p]=++id;
		for(i=k;s[i]!=p;i--) kuai[s[i]]=kuai[p];
		return;
	}
	v1[p]=1;
	v[p]=1;
	for(i=0;i<a[p].size();i++){
		s[k+1]=p;
		dfs(a[p][i],k+1);
	} 
	v[p]=0;
}
void dfs1(int p,int o){
	int i,j;
	if(vis[p]>0) p=vis[p];
	if(o==0) w[p]=0;
	if(v[p]==1) return;
	v[p]=1;
	for(i=0;i<a[p].size();i++){
		dfs1(a[p][i],0);
	}
}
int main(){
	int i,j,x,y,p;
	cin>>n>>p;
	for(i=1;i<=p;i++){
		cin>>x>>y;
		w[x]=y;
	}
	cin>>r;
	for(i=1;i<=r;i++){
		cin>>x>>y;
		a[x].push_back(y);
	}
	for(i=1;i<=n;i++){
		if(v1[i]==0){
	    dfs(i,0);
	    }
	}
	id=n;
	for(i=1;i<=n;i++){
		if(kuai[i]>0){
			int g=kuai[i];
			id++;
			for(j=1;j<=n;j++)
			if(g==kuai[j]){
				vis[j]=id; kuai[j]=0;
				if(w[j]>0){
					if(w[id]==0) w[id]=w[j];
					else w[id]=min(w[id],w[j]);
				}
			}
			for(j=1;j<=n;j++)
			if(vis[j]==id)
			for(x=0;x<a[j].size();x++){
				if(vis[a[j][x]]!=id)
				a[id].push_back(a[j][x]);
			} 
		}
	}
	for(i=1;i<=id;i++) v[i]=0; 
	for(i=1;i<=n;i++)
	if(w[i]>0)
	dfs1(i,1);
	for(i=1;i<=id;i++) 
	if(vis[i]==0&&v[i]==0){
		cout<<"NO\n"<<i;
		return 0;
	}
	for(i=1;i<=id;i++) 
	if(vis[i]==0)
	ans+=w[i];
	cout<<"YES\n";
	cout<<ans;
}
2025/7/24 22:08
加载中...