3672: 间谍网络-【2014暑期训练】T2Day1T3
Description
间谍网络
【问题描述】
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个编号最小的间谍。
【文件输入】
输入文件age.in。
第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。
【文件输出】
输出文件age.out。
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
【输入样例1】
3
2
1 10
2 100
2
1 3
2 3
【输出样例1】
YES
110
【输入样例2】
4
2
1 100
4 200
2
1 2
3 4
【输出样例2】
NO
3
HINT
根据题中给出的间谍的相互控制关系，建立有向图。找出有向图中的所有强连通分量，用每个强连通分量中最便宜的点（需支付最少贿金的间谍）来代替这些强连通分量，将强连通分量收缩为单个节点。收缩强连通分量后的图中，入度为0的节点即代表需要贿赂的间谍。
算法学习：有向图的强连通分量
DFS
DFS就是深度优先搜索，裸的DFS是很启蒙的一个东西，所以就不废话了，直接给出它的程序：
procedure dfs(x:longint);
var j:longint;
begin
flag[x]:=1;
for j:=1 to n do
if (a[x,j]=1)and(flag[j]=0) then
dfs(j);
end;
其中flag是是否遍历过的标记，a是邻接矩阵。
当然，在主程序中需要有这一句：
for i:=1 to n do
if flag[i]=0 then dfs(i);
而不是直接的dfs(1)，因为节点1并不一定能到达所有节点。这是初学者（我？）常犯的一个错误。
当然，DFS进行的顺序并不一定是按节点编号顺序。一般按节点编号顺序DFS只是为了方便，有时我们必须以不同的顺序进行DFS（比如下面将要谈到的Kosaraju算法）。
时间戳与点的分类
设置全局变量time，初始值为0，当遇到一个事件点的时候就+1。时间点分为两种：发现某一节点和结束某一节点（即在DFS过程的开头和结尾）。发现节点x时，发现时间戳d[x]=time；结束节点x时，结束时间戳f[x]=time。
根据时间戳状态的不同可以将节点进行分类：
白点==没有时间戳的节点==未遍历的节点
灰点==仅有发现时间戳的节点==正在遍历以此节点为根的子树的节点
黑点==有发现时间戳和结束时间戳的节点==完成的节点
注意：点的分类随time增长而变化，且DFS结束后所有点都是黑点，所以用一个全局变量保存点的分类没有意义。DFS过程中可以直接通过时间戳得知点的分类。
边的分类
在DFS过程中所有顶点和经过的边形成了一棵DFS树。根据图中的边在DFS树中的位置和发现此边时入节点的分类（这里说的是有向图，每条边有出节点和入节点）将边分为四类：
树枝==DFS树中的边==入节点为白点
反向边==某一节点x到其DFS树中祖先y的边==入节点为灰点
正向边==某一节点x到其DFS树中后代y的边==入节点为黑点==d[x]>d[y]
横叉边==某一节点x到DFS树中另一子树上节点y的边==入节点为黑点==d[x]<d[y]
如下图：
若以节点序号顺序进行DFS，则形成下面一棵DFS树（粗边是树枝，其他类型的边在旁边有说明）
横叉边在图中是只能向左的，通过DFS的过程可以知道这一点。这对我们设计算法很有帮助。
注意，边的分类与点的分类完全不同。点的分类随着时间变化，而边的分类是不变的。所以我们需要用一个全局变量保存边的分类。在后面的程序中，我们用kl[i,j]表示i到j的边的分类，树枝、反向边、正向边、横叉边分别用1/2/3/4表示。
强连通分量
一个有向图中，如果节点i能够通过一些边到达节点j，就简写成i能到达j。如果对于任意两个节点i,j均有i能到达j或j能到达i，则说此图是连通的。如果对于任意两个节点i,j均有i能到达j且j能到达i，则说此图是强连通的。
对于一个无向图，说强联通没有意义，因为此时强连通就是连通。而对于一个有向图，它不一定是强连通的，但可以分为几个极大的强连通子图（“极大”的意思是再加入任何一个顶点就不满足强连通了）。这些子图叫做这个有向图的强连通分量。在上图中，强连通分量是A{1},B{2,4},C{3,5,6,7}。
在一个强连通分量中的节点由于有着相似的拓扑性质，所以我们可以将其紧缩为一个节点（这让我想到了什么？化学里的“族”），于是就大大减小了图的规模。比如上图紧缩为A,B,C三个节点后，整个图就成为了B←A→C的简单形式。所以强连通分量是一个很有意义的东西。然而如果根据定义，对每个节点进行一次O(n2)的DFS以求出它所能到达的顶点的话，整个算法的时间复杂度就是迟钝的O(n3)。下面将介绍两种用O(n2)求强连通分量的算法：Kosaraju算法和Tarjan算法。
Kosaraju算法
Kosaraju算法基于以下思想：强连通分量一定是某种DFS形成的DFS树森林。Kosaraju算法给出了更具体的方式：
①任意进行一次DFS，记录下每个节点的结束时间戳f[i]。
②按f[i]的大小对节点进行排序（从小到大）。
③以②的排序结果为顺序再进行一次DFS，所得的DFS树森林即为强连通分量。这次DFS可以用Floodfill进行，把每个强连通分量标上不同序号。
（这就是OI界传说中的“求强连两遍DFS的算法”）
比如上图，我们可以得到：
d[1]=1 f[1]=14
d[2]=2 f[2]=5
d[3]=6 f[3]=13
d[4]=3 f[4]=4
d[5]=7 f[5]=8
d[6]=9 f[6]=12
d[7]=10 f[7]=11
根据f[i]排序得：④②⑤⑦⑥③①（发现了什么？就是后序遍历），再按照这个顺序进行DFS即可。
程序：
var
a:array[1..1000,1..1000]of longint;
b,flag:array[1..1000]of longint;
n,i,j,m,k:longint;
procedure dfs(x:longint);
var j:longint;
begin
flag[x]:=1;
for j:=1 to n do
if (flag[j]=0)and(a[x,j]>0) then dfs(j);
inc(m);
b[m]:=x;
end;
procedure
fill(x,k:longint);
var j:longint;
begin
flag[x]:=k;
for j:=n downto 1 do
if (flag[b[j]]=0)and(a[b[j],x]>0) then fill(b[j],k);
end;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
m:=0;
fillchar(flag,sizeof(flag),0);
for i:=1 to n do
if flag[i]=0 then dfs(i);
fillchar(flag,sizeof(flag),0);
k:=0;
for i:=n
downto 1 do
if flag[b[i]]=0 then
begin
inc(k);
fill(b[i],k);
end;
for i:=1 to k do
begin
for j:=1 to n do
if flag[j]=i then write(j,' ');
writeln;
end;
end.
Tarjan算法
Tarjan算法只要一遍DFS，效率高于Kosaraju。它在技术上有了很大改进。它基于的思想是：强连通分量是DFS树中的子树（无论你如何进行DFS）。
Tarjan算法的过程是：
①在DFS树中，设low[x]是x或x的后代能够达到的最高的祖先。初始化时low[x]设为x。
②进行DFS，在结束节点x时计算low[x]。计算的方法是：找出x能够到达的所有节点i，应保证low[i]是x的祖先，即low[i]是灰点。low[x]=highest(low[i])，即d[low[i]]最小。
③若low[x]=x，则以x为根的子树就是一个强连通分量，输出并将其从树中删去。
比如上图（又是上图。。没办法，图片空间有限制），我们依次得出：
low[4]=low[2]=2
low[2]=low[4]=2 //{4,2}为强连通分量
low[5]=low[3]=3
low[7]=low[5]=3
low[6]=low[7]=3
low[3]=low[6]=3 //{5,7,6,3}为强连通分量
low[1]=1 //{1}为强连通分量
在实际编写中，我利用了不断输出，发现强连通分量换行的技术，使程序更加简单。
程序：
var a,kl:array[1..1000,1..1000]of longint;
d,f,low:array[1..1000]of longint;
i,j,n,time:longint;
procedure
dfs(x:longint);
var i:longint;
begin
inc(time);
d[x]:=time;
for i:=1 to n do
if a[x,i]>0 then
begin
if d[i]=0 then
begin
kl[x,i]:=1;
dfs(i);
end;
if (d[i]>0)and(f[i]=0) then kl[x,i]:=2;
if f[i]>0 then
begin
if d[x]>d[i] then kl[x,i]:=3 else
kl[x,i]:=4;
end;
end;
inc(time);
f[x]:=time;
write(x,' ');
for i:=1 to n do
if a[x,i]>0 then
if (f[low[i]]=0)and(d[low[i]]<d[low[x]]) then
low[x]:=low[i];
if low[x]=x then writeln;
end;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
fillchar(d,sizeof(d),0);
fillchar(d,sizeof(d),0);
for i:=1 to n do low[i]:=i;
time:=0;
for i:=1 to n do
if d[i]=0 then dfs(i);
end.