社区讨论
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 条回复,欢迎继续交流。
正在加载回复...