代码求调
查看原帖
代码求调
199459
Masna_Kimoyo楼主2021/5/2 13:27

Rt,38分,bzd哪错了

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5,M=8e3+5,INF=2147483647;
struct node{
	int to,next;
}Edge[M];
stack<int> s;
int ans,n,p,r,tot,num,cnt;
int dfn[N],low[N],sum[N],head[N],money[N],in[N],belong[N];
//int out[N];
bool vis[N];
inline int read()
{
	int x=0;
	bool w=0;
	char c=getchar();
	while(!isdigit(c))
		w|=c=='-',c=getchar();
	while(isdigit(c))
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void add(int u,int v)
{
	Edge[++tot].to=v;
	Edge[tot].next=head[u];
	head[u]=tot;
}
inline void Tarjan(int u)
{
	dfn[u]=low[u]=++num;
	s.push(u);
	vis[u]=1;
	for(register int i=head[u];i;i=Edge[i].next)
	{
		int v=Edge[i].to;
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else
		{
			if(vis[v])
				low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		++cnt;
		int t;
		while(t!=u)
		{
			t=s.top();
			s.pop();
			belong[t]=cnt;
			sum[cnt]=min(sum[cnt],money[t]);
			vis[t]=0;
		}
	}
}
int main()
{
	n=read(),p=read();
	for(register int i=1;i<=n;++i)
		sum[i]=INF,money[i]=INF;
	for(register int i=1;i<=p;++i)
	{
		int u=read(),m=read();
		money[u]=m;
	}
	r=read();
	for(register int i=1;i<=r;++i)
	{
		int u=read(),v=read();
		add(u,v);
	}
	for(register int i=1;i<=n;++i)
		if(!dfn[i] && money[i])	
			Tarjan(i);

	for(register int i=1;i<=n;++i)
		if(!dfn[i])
		{
			printf("NO\n%d",i);
			return 0;
		}

	for(register int i=1;i<=n;++i)
		for(register int j=head[i];j;j=Edge[j].next)
		{
			int v=Edge[j].to;
			if(belong[i]!=belong[v])
			{
//				++out[belong[i]];
				++in[belong[v]];
			}
		}
/*
	for(register int i=1;i<=n;++i)
		if(!money[i] && !out[i])
		{
			printf("NO\n%d",i);
			return 0;
		}
*/
	for(register int i=1;i<=n;++i)
		if(!in[i])
			ans+=sum[i];
	printf("YES\n%d",ans);
	return 0;
}
2021/5/2 13:27
加载中...