| |
|
|
| |
描述 Description |
|
| |
由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍（n不超过3000），每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。 |
| |
|
|
| |
|
|
| |
输入格式 Input Format |
|
| |
一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1<=p<=n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000.
紧跟着一行只有一个整数r，1<=r<=8000。然后r行，每行两个正整数，表示数对（A，B），A间谍掌握B间谍的证据。 |
| |
|
|
| |
|
|
| |
输出格式 Output Format |
|
| |
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。 |
| |
|
|
| |
|
|
| |
样例输出 Sample Output [复制数据] |
|
| |
|
| |
|
|
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000;
int V,E;//点数(1) 边数
struct edge//邻接表
{
int t,w;//u->t=w;
int next;
};
int p[maxn];//表头节点
edge G[maxn];
int l;
void init()
{
memset(p,-1,sizeof(p));
l=0;
}
//添加边
void addedge(int u,int t,int w,int l)//u->t=w;
{
G[l].w=w;
G[l].t=t;
G[l].next=p[u];
p[u]=l;
}
//tarjan算法 求有向图强联通分量
int dfn[maxn],lowc[maxn];
//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点
int belg[maxn];//第i个节点属于belg[i]个强连通分量
int stck[maxn],stop;//stck栈
int instck[maxn];//第i个节点是否在栈中
int scnt;//强联通分量
int index;
void dfs(int i)
{
dfn[i]=lowc[i]=++index;
instck[i]=1;//节点i入栈
stck[++stop]=i;
for(int j=p[i];j!=-1;j=G[j].next)
{
int t=G[j].t;
//更新lowc数组
if(!dfn[t])//t没有遍历过
{
dfs(t);
if(lowc[i]>lowc[t]) lowc[i]=lowc[t];
}//t是i的祖先节点
else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];
}
//是强连通分量的根节点
if(dfn[i]==lowc[i])
{
scnt++;
int t;
do
{
t=stck[stop--];
instck[t]=0;
belg[t]=scnt;
}while(t!=i);
}
}
int tarjan()
{
stop=scnt=index=0;
memset(dfn,0,sizeof(dfn));
memset(instck,0,sizeof(instck));
for(int i=1;i<=V;i++)
{
if(!dfn[i]) dfs(i);
}
return scnt;
}
//...
int pl;
int price[maxn];
int flag[maxn];
//........
//缩点
int n;//缩点后的点个数1~n
int g[maxn];
edge eg[maxn];//邻接表
int re;
int in[maxn],out[maxn];
void dinit(int sig)
{
memset(g,-1,sizeof(g));
n=sig;
re=0;
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
}
void addedge0(int u,int t,int w,int l)
{
eg[l].w=w;
eg[l].t=t;
eg[l].next=g[u];
g[u]=l;
}
int main()
{
while(scanf("%d",&V)==1)
{
memset(price,0,sizeof(price));
memset(flag,0,sizeof(flag));
scanf("%d",&pl);
for(int i=0;i<pl;i++)
{
int x,w;
scanf("%d%d",&x,&w);
if(!price[x]) price[x]=w;
else price[x]=min(price[x],w);
}
init();
scanf("%d",&E);
for(int i=0;i<E;i++)
{
int u,t,w=1;
scanf("%d%d",&u,&t);
addedge(u,t,w,l++);
}
int ans=tarjan();
//printf("%d/n",ans);
//缩点
dinit(ans);
for(int i=1;i<=V;i++)//构图
{
for(int j=p[i];j!=-1;j=G[j].next)
{
int st=belg[i],ed=belg[G[j].t];
if(st!=ed)
{
int flag=1;
for(int k=g[st];k!=-1;k=eg[k].next)
{
if(eg[k].t==ed)
{
flag=0;
break;
}
}
if(flag) addedge0(st,ed,1,re++);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=g[i];j!=-1;j=eg[j].next)
{
in[eg[j].t]++,out[i]++;
}
}
int in0=0;
for(int i=1;i<=n;i++)
{
if(in[i]==0) in0++;
}
int st=0;
int sum=0;
for(int i=1;i<=V;i++)
{
if(price[i]==0) continue;
if(in[belg[i]]==0&&flag[belg[i]]==0)
{
flag[belg[i]]=price[i];
st++;
sum+=price[i];
}
else if(in[belg[i]]==0&&flag[belg[i]])
{
if(price[i]<flag[belg[i]])
{
sum+=price[i]-flag[belg[i]];
flag[belg[i]]=price[i];
}
}
}
if(st==in0)
{
printf("YES/n%d/n",sum);
}
else
{
int id;
for(int i=1;i<=V;i++)
{
if(in[belg[i]]==0&&flag[belg[i]]==0)
{
id=i;break;
}
}
printf("NO/n%d/n",id);
}
}
return 0;
}