样例2WA掉/kel
查看原帖
样例2WA掉/kel
360511
UperFicial楼主2021/8/3 17:44
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<climits>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9+10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
inline int Abs(int x){return x>0?x:-x;}
const int MAXN(3010);
const int MAXM(8010);
int n,p,m;
int head[MAXN],tot;
struct E{int to,nxt;};
E edge[MAXM];
inline void add_edge(int u,int v)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	return;
}
int low[MAXN],dfn[MAXN];
bool vis[MAXN];
int st[MAXN],siz,cnt,t;
int pos[MAXN];
inline void tarjan(int u)
{
	low[u]=dfn[u]=++t;
	vis[u]=true;
	st[++siz]=u;
	for(register int i=head[u];i;i=edge[i].nxt)
	{
		E e=edge[i];
		if(!dfn[e.to])
		{
			tarjan(e.to);
			low[u]=Min(low[u],low[e.to]);
		}
		else if(vis[e.to]) low[u]=Min(low[u],low[e.to]);
	}
	if(low[u]==dfn[u])
	{
		++cnt;
		while(st[siz]!=u)
		{
			int v=st[siz];
			--siz;
			vis[v]=false;
			pos[v]=cnt;
		}
		--siz;
		vis[u]=false;
		pos[u]=cnt;
	}
	return;
}
int in[MAXN];
int ans;
struct node{int v,id;};
node a[MAXN];
inline bool cmp(node x,node y){return x.v<y.v;}
E ed[MAXM];
int head2[MAXN],tot2;
inline void add_edge2(int u,int v)
{
	ed[++tot2].nxt=head2[u];
	head2[u]=tot2;
	ed[tot2].to=v;
	return;
}
queue<int>q;
inline int topo_sort()
{
	for(register int i=1;i<=p;i++)
		q.push(pos[a[i].id]);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(register int i=head2[u];i;i=ed[i].nxt)
		{
			E e=ed[i];
			if(in[e.to]==0) continue;
			if(--in[e.to]==0)
				q.push(e.to);
		}
	}
	for(register int i=1;i<=n;i++)
		if(pos[i]==i&&vis[i]==0) return i;
	return -1;
}
int main()
{
	n=read(),p=read();
	for(register int i=1;i<=p;i++)
		a[i].id=read(),a[i].v=read();
	sort(a+1,a+1+p,cmp);
	m=read();
	while(m--)
	{
		int u=read(),v=read();
		add_edge(u,v);
	}
	for(register int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	memset(vis,0,sizeof(vis));
	for(register int i=1;i<=n;i++)
		for(register int j=head[i];j;j=edge[j].nxt)
		{
			E e=edge[j];
			if(pos[i]==pos[e.to]) continue;
			add_edge2(pos[i],pos[e.to]);
			++in[pos[e.to]];
		}
	int use[MAXN];
	for(register int i=1;i<=cnt;i++)
		use[i]=in[i];
	int now=topo_sort();
	for(register int i=1;i<=cnt;i++)
		in[i]=use[i];
	if(now!=-1)
	{
		puts("NO");
		printf("%d\n",now);
		return 0;
	}
	memset(vis,0,sizeof(vis));
	for(register int i=1;i<=p;i++)
	{
		if(use[pos[a[i].id]]||vis[pos[a[i].id]]) continue;
		ans+=a[i].v;
		vis[pos[a[i].id]]=true;
	}
	puts("YES");
	printf("%d\n",ans);
}
2021/8/3 17:44
加载中...