54分求助,WA#2 #4 #6 #7 #11 #13
查看原帖
54分求助,WA#2 #4 #6 #7 #11 #13
393977
w13737245882楼主2022/4/3 10:47
include<bits/stdc++.h>
using namespace std;
struct{
	int u;
	int v;
	int next;
}e[1000009];
int in[3009],f[10009],n,p,vis[3009],m,cnt,a[3009],head[1000009];
int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
void add(int u,int v)
{
	cnt++;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(!vis[v])
		{
			vis[v]=vis[u]+1;
			dfs(v);
		}
		int fu=find(u),fv=find(v);
		if(vis[fv] > 0)
		{
            if(vis[fu] < vis[fv]) f[fv] = fu;
            else f[fu] = fv;
        }
	}
	vis[u]=-1;
}
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++)
	{
		a[i]=0x7ffffff;
		f[i]=i;
	}
	for(int i=1;i<=p;i++)
	{
		int x,w;
		scanf("%d%d",&x,&w);
		a[x]=w;
	}
	int r;
	scanf("%d",&r);
	for(int i=1;i<=r;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]&&a[i]!=0x7ffffff)
		{
			vis[i]=-1;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0) 
		{
			cout<<"NO"<<endl<<i;
			return 0;
		}
	}
	for(int i=1;i<=r;i++)
	{
		if(f[e[i].u]!=f[e[i].v]) in[e[i].v]++;
		else a[f[e[i].u]]=min(a[e[i].u],a[e[i].v]);
	}
	/*for(int j=1;j<=n;j++)
	{
		for(int i=head[j];i;i=e[i].next)
		{
			if(f[e[i].u]!=f[e[i].v]) in[e[i].v]++;
			else a[f[e[i].u]]=min(a[e[i].u],a[e[i].v]);
		}
	}*/
	int ans=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		if(!in[f[i]]&&!vis[f[i]])
		{
			vis[f[i]]=1;
			ans+=a[f[i]];
		}
	}
	cout<<"YES"<<endl<<ans;
	return 0;
}
2022/4/3 10:47
加载中...