首页 > 代码库 > tyvj 1153 间谍网络 tarjan有向图强连通
tyvj 1153 间谍网络 tarjan有向图强连通
P1153 - 间谍网络
From ForeverBell Normal (OI)总时限：13s 内存限制：128MB 代码长度限制：64KB
描述 Description
由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍（n不超过3000），每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
输入格式 InputFormat
一行只有一个整数n。第二行是整数p。表示愿意被收买的人数，1<=p<=n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000.
紧跟着一行只有一个整数r，1<=r<=8000。然后r行，每行两个正整数，表示数对（A，B），A间谍掌握B间谍的证据。
输出格式 OutputFormat
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。样例输入 SampleInput [复制数据]
2
1
2 512
2
1 2
2 1
样例输出 SampleOutput [复制数据]
YES
512
一道很裸的tarjan题，但明显我的tarjan学了跟没学一样，很多小细节没有注意（更新low什么时候用dfn，什么时候用low；tarjan完了要把点从图中删除）。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>using namespace std;#define MAXN 10000#define MAXE MAXN * 2#define MAXV MAXN#define INF 0x3f3f3f3fint n,m;struct Edge{ int np; Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y){ E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope];}int state[MAXN];int value[MAXN];int dfn[MAXN],low[MAXN],dfstime=0;int stack[MAXN],tops=-1;int color[MAXN],totc=0;void tarjan(int now){ low[now]=dfn[now]=++dfstime; Edge *ne; stack[++tops]=now; for (ne=V[now];ne;ne=ne->next) { if (dfn[ne->np])//state[ne->np]==1 { if (color[ne->np])continue; low[now]=min(low[now],dfn[ne->np]); }else { tarjan(ne->np); low[now]=min(low[now],low[ne->np]);//易写反 } } if (low[now]==dfn[now]) { totc++; while (stack[tops]!=now) { color[stack[tops--]]=totc; } color[stack[tops--]]=totc; }}int main(){// freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout); int t; int x,y; int i,j,k; scanf("%d",&n); memset(value,INF,sizeof(value)); scanf("%d",&t); for (i=0;i<t;i++) { scanf("%d%d",&x,&y); value[x]=y; } scanf("%d",&m); for (i=0;i<m;i++) { scanf("%d%d",&x,&y); addedge(x,y); } for (i=1;i<=n;i++) { if (!dfn[i]) { tarjan(i); } } Edge *ne; for (i=1;i<=n;i++) { for (ne=V[i];ne;ne=ne->next) { if (color[ne->np]==color[i])continue; state[color[ne->np]]=true; } } x=INF; bool ok=true; int ans=0; int ans2=INF; for (i=1;i<=totc;i++) { if (state[i])continue; x=INF; for (j=1;j<=n;j++) { if (color[j]!=i)continue; x=min(x,value[j]); } if (x==INF) { ok=false; for (j=1;j<=n;j++) { if (color[j]==i) { ans2=min(ans2,j); break; } } } ans+=x; } if (!ok) { printf("NO\n%d\n",ans2); }else { printf("YES\n%d\n",ans); }}
v
tyvj 1153 间谍网络 tarjan有向图强连通
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。