社区讨论

yes误判为no 70求助

P1262[POI 1996 R3] 间谍网络参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo8hgcmf
此快照首次捕获于
2023/10/27 18:41
2 年前
此快照最后确认于
2023/10/27 18:41
2 年前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>

const int maxn=3005;

using namespace std;

int n,m,d,tim,zjh,t,sum;
int ind[maxn],hd[maxn],a[maxn],ap[maxn],dfn[maxn],low[maxn],flag[maxn],vis[maxn],p[maxn],isin[maxn];
vector<int>g[maxn];
deque<int>q;

struct edge {
	int u,v,nxt;
} e[maxn*3];

void addedge(int u,int v) {
	e[++t].u=u;
	e[t].v=v;
	e[t].nxt=hd[u];
	hd[u]=t;
}
void tarjan(int u) {
	vis[u]=flag[u]=1;
	dfn[u]=low[u]=++tim;
	q.push_back(u);
	for(int i=0; i<g[u].size(); i++) {
		int v=g[u][i];
		if(vis[v]&&flag[v])
			low[u]=min(low[u],dfn[v]);
		if(!vis[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
	}
	if(dfn[u]==low[u]) {
		zjh++;
		while(1) {
			int y=q.back();
			p[y]=zjh;
			flag[y]=0;
			q.pop_back();
			if(y==u)break;
		}
	}
}
int main() {
	freopen("P1262 .in","r",stdin);
	freopen("p1262.out","w",stdout);
	scanf("%d%d",&n,&d);
	for(int i=1,x,y; i<=d; i++) {
		scanf("%d%d",&x,&y);
		a[x]=y;
	}
	scanf("%d",&m);
	for(int i=1,u,v; i<=m; i++) {
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i])
			tarjan(i);
	memset(ap,0x7f,sizeof(ap));
	for(int i=1; i<=n; i++)
		ap[p[i]]=min(a[i],ap[p[i]]);
	for(int u=1; u<=n; u++) {
		for(int i=0; i<g[u].size(); i++) {
			int v=g[u][i];
			//printf("%d %d\n",u,p[v]);
			if(p[u]==p[v])continue;
			addedge(p[u],p[v]);
			ind[p[v]]++;
		}
	}
	
	for(int i=1; i<=n; i++) {
		if(ind[p[i]]==0) {
			if(ap[p[i]]==0) {
				puts("NO");
				printf("%d",i);
				return 0;
			}
			if(!isin[p[i]]) {
				sum+=ap[p[i]];
				isin[p[i]]=1;
			}
		}
	}
	puts("YES");
	printf("%d",sum);
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...