w | Hexo

归档于 2019-10-02 06:27

dp

题解

首先第一问就是奇度点个数/2

直接$dp$不好$dp$,考虑关于奇度点来设立

边权下放到节点

$f[x][0/1]$结构体定义,$f[x][0].c1$表示$x$与父亲连边不反转时奇度点个数,$f[x][0].c2$表示$x$与父亲连边翻转是要的最小操作数$f[x][1]$表示翻转

转移就是分情况讨论,我们首先要将子树合并完,最后再上传到当前节点

w1表示子树有一条边指向当前节点代价(奇度点个数为奇)

w2表示子树没有边指向当前节点代价(奇度点个数为偶)

分别转移

$w1=min(w2+f[y][1],w1+f[y][0])$

解释一下保证奇度点个数为奇可以是当前已考虑子树 内两两合,并翻转当前这条边;或者已考虑子树 内伸出一条边当前边不伸

$w2=min(w1+f[y][1],w2+f[y][0])$

和上面类似

那么对于当前来说

$f[x][0]$由两部分转移,可以是没操作$w2$可以当前点和子树一奇度点结合$c1=w1.c1+1,c2=w1.c2$(路径长度不+1是因为在下面统计过了)

$f[x][1]$由两部分转移,可以是让子树伸的边继续延伸$c1=w1.c1,c2=w1.c2+1$可以是当前边翻转然后当前点成为奇点$c1=w2.c1+1,c2=w2.c2+1$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e9+7
#define A 1111111
ll head[A],nxt[A],ver[A],edg[A];
ll tot,n;
void add(ll x,ll y,ll opt){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edg[tot]=opt;
}
struct node{
    ll c1,c2;
    node(){}
    node (const ll &a,const ll &b){
        c1=a,c2=b;
    }
    friend bool operator < (const node &a,const node &b){
        return (a.c1==b.c1)?(a.c2<b.c2):(a.c1<b.c1);
    }
    friend node operator +(const node &a,const node &b){
        node c;c.c1=0,c.c2=0;
        c.c1=a.c1+b.c1,c.c2=a.c2+b.c2;
        return c;
    }
}f[A][2];
void dfs(ll x,ll pre,ll opt){
    node w1(inf,inf),w2(0,0),n1,n2;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==pre) continue ;
        dfs(y,x,edg[i]);
        n1=min(w1+f[y][0],w2+f[y][1]);
        n2=min(w2+f[y][0],w1+f[y][1]);
        w1=n1,w2=n2;
    }
//    printf("w1.c1=%lld w1.c2=%lld w2.c1=%lld w2.c2=%lld\n",w1.c1,w1.c2,w2.c1,w2.c2);
    if(opt==2){
        f[x][1]=min(node(w1.c1,w1.c2+1),node(w2.c1+1,w2.c2+1));
        f[x][0]=min(node(w1.c1+1,w1.c2),node(w2.c1,w2.c2));
    }
    else if(opt==1){//must
        f[x][1]=min(node(w1.c1,w1.c2+1),node(w2.c1+1,w2.c2+1));
        f[x][0]=node(inf,inf);
    }
    else if(opt==0){//must`not
        f[x][0]=min(node(w1.c1+1,w1.c2),node(w2.c1,w2.c2));
        f[x][1]=node(inf,inf);
    }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<n;i++){
        ll x,y,opt,case1,case2;
        scanf("%lld%lld%lld%lld",&x,&y,&case1,&case2);
        if(case2==2){
            add(x,y,2);add(y,x,2);
        }
        else if(case1==case2){
            add(x,y,0);add(y,x,0);
        }
        else if(case1!=case2){
            add(x,y,1);add(y,x,1);
        }
    }
    dfs(1,0,0);
    printf("%lld %lld\n",f[1][0].c1>>1,f[1][0].c2);
}

View Code