[APIO2010 patrol]树形动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
就是求两(一)条不相交的最长链。
F[i][j][k]表示i这个结点,已完成的链有j条,k表示有无一条只有一边的可延伸链,所得到的最大长度。
然后就像背包一样转移。
【CODE】
#include #include #include const int N=100005;
struct edge{int x,y;edge *next;}sp[N*2],*ls[N];
int n,L,e,tot;
int F[N][3][2],pF[3][2];

inline void addedge(int x,int y){
sp[++e].x=x; sp[e].y=y; sp[e].next=ls[x]; ls[x]=&sp[e];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y;
scanf("%d%d",&n,&L);
for (i=1;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) dp(t->y,t->x);
F[p][0][0]=0;
F[p][0][1]=0;
int j,k,pj,pk;
tot=0;
for (edge *t=ls[p];t;t=t->next) if (t->y!=fa){
memcpy(pF,F[p],sizeof(pF));
for (j=0;j<=L;j++)
for (pj=0;pj+j<=L;pj++){
F[p][pj+j][0]=max(F[p][pj+j][0],pF[pj][0]+F[t->y][j][0]);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][0]+F[t->y][j][1]+1);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][1]+F[t->y][j][0]);
if (pj+j+1<=L)
F[p][pj+j+1][0]=max(F[p][pj+j+1][0],pF[pj][1]+F[t->y][j][1]+1);
}
}
}

void solve(){
int ans=0;
memset(F,200,sizeof(F));
dp(1,0);
ans=max(ans,F[1][1][0]);
ans=max(ans,F[1][0][1]);
if (L==2){
ans=max(ans,F[1][1][1]);
ans=max(ans,F[1][2][0]);
}
printf("%dn",2*n-2-ans+L);
}

int main(){
freopen("patrol.in","r",stdin);
freopen("patrol.out","w",stdout);
init();
solve();
return 0;
}

加入对话

10条评论

  1. 回复RP小魚兒:当时有一个人说了一种贪心,就是先找一条最大权链,然后把链上边权置为-1,然后再找一条最大权链。可能是这种?MS和最大流的修正差不多。。。

  2. 回复哈凌大侠:你想想背包问题吧。现在假设下面有x条链伸上来。如果x是奇数,那么这个k=1。表示可以向父亲连。如果x是偶数,那么这个k=0。这样他们下面就已经一一配对好。练成链弄到一起了。不知道这样你懂了吗?

  3. 有两句不太理解 F[p][pj+j+1][0]=max(F[p][pj+j+1][0],pF[pj][1]+F[t->y][j][1]+1);本来不可以和父亲连,却转移出来了pF[pj][1],为什么呢 ans=max(ans,F[1][1][1]);1节点不是没有父亲吗?怎么和父亲连呢?麻烦请大牛解释一下

  4. 回复哈凌大侠:我的一个状态本质上是:已经配对好了j“对”链。然后第3维表示的是,现在是否有未配对的单链延伸到本点。

留下评论

您的电子邮箱地址不会被公开。