tyvj客户端?棋盘覆盖?【TYVj p1153,极其强大的缩点】网络

你是否正在寻找关于tyvj的内容？让我把最新的东西奉献给你：

Tarjan是一种很高效的求解有向图的强连通分量的算法，但是它的主要应用之一是缩点，也就是把整个强连通分量的一定信息集中到一个点上，将其构成一个新图，。由于所有强连通分量的并集是所有点的并集，所以整个图的相应性质不变。

很明显，这道题与节点的度有关。如果一个点的入度为0，则我们必然要贿赂他。但是如果单纯的考虑度就错了。我们忽略了一种入度全部大于0的情况——环。样例就是一个例子。这时如果我们再拓扑找环再去找最小值，我们就会花大量时间（毕竟边很多）。这时就要用到Tarjan缩点。

我们把图G转化成一个由代表强连通分量的点构成的G’。我们只需记录该分量中最小的节点权值。然后在G’中找到入度为0的点，枚举是否能被贿赂，如果不能则输出NO，否则累加，到最后输出。

参考代码：

program tvyj1153; var v,f:array[1..3000]of boolean; a:array[0..3000,0..3000]of integer; b:array[1..3000,1..3000]of boolean; i,j,n,m,p,x,y:integer; num,deep,nd:integer; minn:integer; va,du,mc,rd:array[1..3000]of integer; tot:longint; dfn,low,stack:array[1..3000]of integer; function min(x,y:integer):integer; begin if x>y then exit(y) else exit(x); end; procedure zoom(x:integer); var list:array[1..3000]of integer; i,j:integer; d,l:integer; min,mint:integer; begin min:=32767; mint:=32767; d:=0; l:=0; while stack[num]<>x do begin inc(l); list[l]:=stack[num]; f[stack[num]]:=false; dec(num); end; f[stack[num]]:=false; inc(l); list[l]:=stack[num]; dec(num); for i:=1 to l do begin if list[i]<mint then mint:=list[i]; d:=d+rd[list[i]]; //累加整个分量的度 if(va[list[i]]>0)and(va[list[i]]<min)then min:=va[list[i]]; end; for i:=1 to l do for j:=1 to l do if(i<>j)and(b[list[i],list[j]])then dec(d); //减去分量内部的度 if(d=0)and(min=32767)then if mint<minn then minn:=mint; //记录入度为0且不能被贿赂的最小点 inc(nd); //nd记录了G’中节点的个数 du[nd]:=d; mc[nd]:=min; end; procedure dfs(x:integer); var i:integer; begin inc(deep); dfn[x]:=deep; low[x]:=deep; inc(num); stack[num]:=x; f[x]:=true; for i:=1 to a[x,0] do if not v[a[x,i]]then begin v[a[x,i]]:=true; dfs(a[x,i]); low[x]:=min(low[x],low[a[x,i]]); end else if f[a[x,i]] then low[x]:=min(low[x],low[a[x,i]]); if low[x]=dfn[x] then zoom(x); end; procedure get; var i:integer; begin if minn<>32767 then //检查是否能 begin writeln('NO'); writeln(minn); end else begin for i:=1 to nd do if du[i]=0 then tot:=tot+mc[i]; writeln('YES'); writeln(tot); end; end; begin readln(n); readln(p); fillchar(f,sizeof(f),false); fillchar(v,sizeof(v),false); fillchar(b,sizeof(b),false); minn:=32767; for i:=1 to p do begin read(x); readln(va[x]); end; readln(m); for i:=1 to m do begin readln(x,y); inc(a[x,0]); a[x,a[x,0]]:=y; b[x,y]:=true; //b数组记录连通性 inc(rd[y]); //记录每个点的入度 end; for i:=1 to n do if not v[i] then dfs(i); get; end.

本文地址：

（saltless原创，转载请注明出处）

以上就是关于tyvj的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-11562-1.html