生活随笔
收集整理的這篇文章主要介紹了
2019.02.07 bzoj4316: 小C的独立集（仙人掌+树形dp）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
題意：給出一個仙人掌森林求其最大獨立集。
思路：如果沒有環可以用經典的樹形dpdpdp解決。
fi,0/1f_{i,0/1}fi,0/1?表示第iii個點不選/選的最大獨立集。
然后fi,0+=max{fv,0,fv,1},fi,1+=fv,0f_{i,0}+=max\{f_{v,0},f_{v,1}\},f_{i,1}+=f_{v,0}fi,0?+=max{fv,0?,fv,1?},fi,1?+=fv,0?轉移即可。
現在有了環考慮把每個環單獨提出來更新一下。
就用個隊列把整個環記錄下來然后分這個環在原圖中dfsdfsdfs出來的最高點選與不選分別dpdpdp更新即可。
代碼：
#include<bits/stdc++.h>
#define ri register int
using namespace std
;
inline int read(){int ans
=0;char ch
=getchar();while(!isdigit(ch
))ch
=getchar();while(isdigit(ch
))ans
=(ans
<<3)+(ans
<<1)+(ch
^48),ch
=getchar();return ans
;
}
const int N
=5e4+5;
int n
,m
,ans
=0,fa
[N
],dfn
[N
],low
[N
],tot
=0,f
[N
][2],g
[N
][2],q
[N
],top
;
vector
<int>e
[N
];
inline void solve(int rt
,int x
){int tmp0
=f
[rt
][0],tmp1
=f
[rt
][1],tmp
=x
;q
[top
=1]=x
;while(x
!=rt
)x
=fa
[x
],q
[++top
]=x
;x
=tmp
;g
[x
][0]=f
[x
][0],g
[x
][1]=-0x3f3f3f3f;for(ri i
=2;i
<=top
;++i
){g
[q
[i
]][0]=f
[q
[i
]][0]+max(g
[q
[i
-1]][0],g
[q
[i
-1]][1]);g
[q
[i
]][1]=f
[q
[i
]][1]+g
[q
[i
-1]][0];}tmp1
=max(tmp1
,g
[rt
][1]);g
[x
][0]=f
[x
][0],g
[x
][1]=f
[x
][1];for(ri i
=2;i
<=top
;++i
){g
[q
[i
]][0]=f
[q
[i
]][0]+max(g
[q
[i
-1]][0],g
[q
[i
-1]][1]);g
[q
[i
]][1]=f
[q
[i
]][1]+g
[q
[i
-1]][0];}tmp0
=max(tmp0
,g
[rt
][0]);f
[rt
][0]=tmp0
,f
[rt
][1]=tmp1
;
}
void tarjan(int p
){dfn
[p
]=low
[p
]=++tot
,f
[p
][1]=1;for(ri i
=0,v
;i
<e
[p
].size();++i
){if((v
=e
[p
][i
])==fa
[p
])continue;if(!dfn
[v
])fa
[v
]=p
,tarjan(v
),low
[p
]=min(low
[p
],low
[v
]);else low
[p
]=min(low
[p
],low
[v
]);if(dfn
[p
]<low
[v
])f
[p
][0]+=max(f
[v
][0],f
[v
][1]),f
[p
][1]+=f
[v
][0];}for(ri i
=0,v
;i
<e
[p
].size();++i
)if(fa
[v
=e
[p
][i
]]!=p
&&dfn
[p
]<dfn
[v
])solve(p
,v
);
}
int main(){n
=read(),m
=read();for(ri i
=1,u
,v
;i
<=m
;++i
)u
=read(),v
=read(),e
[u
].push_back(v
),e
[v
].push_back(u
);for(ri i
=1;i
<=n
;++i
)if(!dfn
[i
])tarjan(i
),ans
+=max(f
[i
][0],f
[i
][1]);cout
<<ans
;return 0;
}
轉載于:https://www.cnblogs.com/ldxcaicai/p/10367707.html
總結
以上是生活随笔為你收集整理的2019.02.07 bzoj4316: 小C的独立集（仙人掌+树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
