[jzoj]1729.blockenemy

Link

　　https://jzoj.net/senior/#main/show/1729

Description

　　你在玩电子游戏的时候遇到了麻烦。。。。。。

　　你玩的游戏是在一个虚拟的城市里进行，这个城市里有n个点，都从0~n-1编了号，每两个点之间有且仅有一条路径。现在，你的敌人到这个城市来踩点了!!!为了阻止他们更好的踩点， 你决定切断他们所有踩点人员的联系，使他们孤军作战，然后在各个击破。但是这就要切断某些街道，而你每切断一条路，市民就会产生相对的不满值，不满值越大，城市的和谐度就越小。

　　所以你现在需要知道为了使踩点人员所在的点两两之间不联通所切断的边产生的最小不满值是多少？

Solution

40分

　　判断每条边选不选，就可以了

100分

　　这道题是一道很好的树形DP练手题目，同时也可以用并查集+贪心来做，现在讲一下两种做法

（1）树形DP

　　设f[x]表示以x为根，它子树的敌人都不可以互相联络，且无法到达点x的最小价值

　　设g[x]表示以x为根，它子树的敌人都不可以互相联络，但是其中一个敌人可以到达x这个点的最小价值

　　这个状态设得异常巧妙，在我看过这道题的所有题解，这是最好理解的

　　其实，解题的关键，就是状态和转移上面了！

　　我们考虑两种情况，如果当前x上有敌人，或者没有敌人，应该怎么做。

　　①有敌人 

　　如果有敌人，那么f[x]就赋值为无穷大，因为他根本不可以“无法到达点x” 

　　这时，我们考虑g[x]给之后的转移用，到底g[x]应该是多少 

　　显然是g[x]=∑min(f[y],g[y]+dis[x,y])，（y是x的儿子）为什么呢？ 

　　因为x这个点有敌人了，那么g[x]本身就符合条件了 

　　因为f[y]的时候，没有点可以互相联络，如果多添一个点x，那么他就是g[x]的条件了，所以它是取最小值的两个数之一 

　　因为g[y]已经符合条件了，如果多添一个点x，那么他就不符合g[x]的条件了，因为他有2个点可以到达x，所以我们需要x~y之间连一条边，保证只有1个点可以到达x 

　   ②无敌人 

　　f[x]=∑min(f[y],g[y]+dis[x,y])（y是x的儿子）为什么呢？ 

　　跟上面g数组的转移差不多 

　　f[y]是符合条件的，所以多添一个点还是fx的条件，所以是取最小值的两个数之一、 

　　g[y]是不符合条件的，他有1个点可以到达x，所以x~y之间连一条边，保证没有点可以到达x 

　　可是，这时，g[x]怎么做的？怎么转移是本题解题的关键所在 

　　g[x]一定是在f[x]的基础上转移的！使得它的某个儿子不可以到达 

　　其实，就是把f[x]中，一个花费最大的一次删除敌人到x的边的价值，删掉 

　　重点 

　　上面说了f[x]=min(f[y],g[y]+dis[x,y])(其中一个)，我们把可以到达x这个点，变成不可以到达这个点，然后就有两种情况 

　　一种就是g[y]+dis，如下图 

 　　

　　试想一下，原本y点为根的子树是可以到达y的，但是删去了x~y之间的边就不可以到达了，也就是说，是从未知点~x~y的，是这样的顺序 

　　还有一种情况就是f[y]，同上图 

　　就是原本的 

　　我们由min(g[y]+dis,f[y])变成g[y]就是上面所说 

　　f[x]就会在f[x]的基础上减去min(g[y]+ w, f[y]) – g[y]，那么这个值越大，f[x]就会越小。

　　f[x]-g[y]就是那个让原本可以到y的，变成不能到y的那条边，f[x]-这条边的最大值，就是g[x]

　　显然是取最大值，这样g[x]就变得很小

　　我发个连续的段子，结合图片和f,g数组的定义看，一定可以看得懂

　　“G[x]的转移有那么一丢丢难想。G[x]一定实在f[x]的基础上，使得某个儿子从不能到达x，变成能到达x，即儿子y对该状态的贡献由min(g[y] + w, f[y])变为g[x].如果这样的话，f[x]就会在f[x]的基础上减去min(g[y]+ w, f[y]) – g[y]，那么这个值越大，f[x]就会越小。”

　　如果实在看不懂，就看看我那含糊不清的理解，说不定，我们心有灵犀，一语点破。

（2）贪心+并查集

　　思想跟最小生成树一样，简直一模一样

　　可以通过O(n^2)判断加多一条边是否可以符合题目条件

　　边从大到小选

　　如果n大一点，上面的判断可以改成O(m)的，m是边数，根据深度来搜索每一个点。

Code（3）

树形DP①

uses math;
var
        n,i,j,x,y,z:longint;
        g,f,e,bz,ok:array[0..500] of longint;
        b,c:array[0..500,0..1000] of longint;
procedure insert(x,y,z:longint);
begin
        inc(b[x,0]);
        b[x,b[x,0]]:=y;
        c[x,b[x,0]]:=z;
end;

procedure dg(x:longint);
var
        t,i,tt:longint;
begin
        if ok[x]=1 then
        begin
                f[x]:=maxlongint;
                for i:=1 to b[x,0] do
                        if bz[b[x,i]]=0 then
                        begin
                                bz[b[x,i]]:=1;
                                dg(b[x,i]);

                                g[x]:=g[x]+min(g[b[x,i]]+c[x,i],f[b[x,i]]);
                        end;
        end
        else
        begin
                t:=0;
                for i:=1 to b[x,0] do
                        if bz[b[x,i]]=0 then
                        begin
                                bz[b[x,i]]:=1;
                                dg(b[x,i]);

                                tt:=min(f[b[x,i]],g[b[x,i]]+c[x,i]);

                                f[x]:=f[x]+tt;

                                t:=max(t,tt-g[b[x,i]]);

                        end;

                g[x]:=f[x]-t;
        end;
end;

begin
        assign(input,'s.in');reset(input);
        readln(n);
        for i:=1 to n-1 do
        begin
                readln(x,y,z);
                insert(x,y,z);
                insert(y,x,z);
        end;

        while not eof do
        begin
                inc(e[0]);
                readln(e[e[0]]);
                ok[e[e[0]]]:=1;
        end;

        bz[0]:=1;
        dg(0);

        writeln(min(f[0],g[0]));
end.

树形DP②

const   maxn=500;
var     i,n,x,y,l,tot:longint;
        yy,next,cost,g,fa,f,gu:array[1..maxn] of longint;
        t:array[1..maxn] of boolean;
function max(x,y:longint):longint; begin if x>y then exit(x);exit(y);end;
function min(x,y:longint):longint; begin if x>y then exit(y);exit(x);end;
procedure make(x,y,l:longint);
begin
        inc(tot);
        yy[tot]:=y;
        next[tot]:=gu[x];
        cost[tot]:=l;
        gu[x]:=tot;
end;
procedure dfs(x:longint);
var     i,j,sum,y:longint;
begin
        i:=gu[x];
        sum:=0;
        while i<>0 do begin
                y:=yy[i];
                if fa[x]<>y then begin
                        fa[y]:=x;
                        dfs(y);
                        if t[y] then begin
                                f[x]:=f[x]+f[y]+cost[i];
                                g[x]:=g[x]+f[y]+cost[i];
                                sum:=max(sum,cost[i]);
                        end else begin
                                f[x]:=f[x]+min(g[y]+cost[i],f[y]);
                                if g[y]+cost[i]>f[y] then begin
                                        sum:=max(sum,f[y]-g[y]);
                                        g[x]:=g[x]+f[y];
                                end else begin
                                        sum:=max(sum,cost[i]);
                                        g[x]:=g[x]+g[y]+cost[i];
                                end;
                        end;
                end;
                i:=next[i];
        end;
        if t[x] then g[x]:=f[x] else g[x]:=g[x]-sum;
end;
begin
        readln(n);
        for i:=1 to n-1 do begin
                readln(x,y,l);
                make(x+1,y+1,l);
                make(y+1,x+1,l);
        end;
        while not eof do begin
                readln(x);
                t[x+1]:=true;
        end;
        dfs(1);
        writeln(min(f[1],g[1]));
end.

贪心+并查集

var
        bz:boolean;
        n,i,j,k,ans:longint;
        f,e,qq:array[0..50] of longint;
        a:array[0..50,0..3] of longint;
procedure q(l,r:longint);
var
        i,j,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=a[(l+r) shr 1,3];
        while i<j do
        begin
                while a[i,3]>mid do inc(i);
                while a[j,3]<mid do dec(j);
                if i<=j then
                begin
                        a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];

                        inc(i); dec(j);
                end;
        end;

        if i<r then q(i,r);
        if l<j then q(l,j);
end;

function getfather(x:longint):longint;
begin
        if f[x]=0 then exit(x);
        f[x]:=getfather(f[x]);
        exit(f[x]);
end;

procedure he(x,y:longint);
var
        fx,fy:longint;
begin
        fx:=getfather(x);
        fy:=getfather(y);
        if fx<>fy then
                f[fy]:=fx;
end;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                readln(a[i,1],a[i,2],a[i,3]);
                inc(a[i,1]);
                inc(a[i,2]);
        end;

        while not eof do
        begin
                inc(e[0]);
                readln(e[e[0]]);
                inc(e[e[0]]);
        end;

        q(1,n-1);

        for i:=1 to n-1 do
        begin
                qq:=f;

                if getfather(a[i,1])<>getfather(a[i,2]) then
                        he(a[i,1],a[i,2]);

                bz:=true;
                for j:=1 to e[0] do
                        for k:=1 to e[0] do
                                if j<>k then
                                        if getfather(e[j])=getfather(e[k]) then
                                                bz:=false;
                if not bz then
                begin
                        f:=qq;
                        inc(ans,a[i,3])
                end;
        end;

        writeln(ans);
end.