正題

---

大意

一個(gè)n個(gè)點(diǎn)n條邊的無向圖，在一個(gè)點(diǎn)安電子眼就能監(jiān)視到連接它的邊，要求所有的邊都被監(jiān)視求安放電子眼的最少數(shù)目。

---

解題思路

就是沒一條邊的兩頭都至少得有一個(gè)電子眼。我們先假設(shè)它是n-1條邊的環(huán)
用f[i]f[i]來表示不在這個(gè)點(diǎn)放電子眼的最少電子眼數(shù)目
用g[i]g[i]來表示在這個(gè)點(diǎn)放電子眼的最少電子眼數(shù)目
然后我們可以進(jìn)行推算，一個(gè)點(diǎn)不放電子眼，那么它的子節(jié)點(diǎn)就一點(diǎn)要放。

f[i]=g[son]f[i]=g[son]
如果一個(gè)地方放電子眼，那么它的子節(jié)點(diǎn)就可放可不放
g[i]=max{f[son],g[son]}g[i]=max{f[son],g[son]}
然后我們?cè)谔幚憝h(huán)。發(fā)現(xiàn)環(huán)時(shí)我們可以不去進(jìn)行dp該點(diǎn)但是取該點(diǎn)的結(jié)果。

---

代碼

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node{int to,next; }a[200001]; int ls[100001],g[100001],f[100001],tot,n,k,x,maxs; bool v[100001]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dp(int x) {int s1=1,s2=0;for (int i=ls[x];i;i=a[i].next){if (!v[a[i].to]){v[a[i].to]=1;//標(biāo)記dp(a[i].to);//dps1+=min(g[a[i].to],f[a[i].to]);//動(dòng)態(tài)轉(zhuǎn)移}s2+=g[a[i].to];//處理環(huán)（因?yàn)楦腹?jié)點(diǎn)沒有值所以不會(huì)有影響）}g[x]=s1;f[x]=s2;//保證搜完子節(jié)點(diǎn)之前父節(jié)點(diǎn)沒有值 } int main() {scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&k);for (int j=1;j<=k;j++)scanf("%d",&x),addl(i,x);}v[1]=1; dp(1);printf("%d",min(f[1],g[1]));//輸出 }

總結(jié)

以上是生活随笔為你收集整理的jzoj1029-电子眼【树形dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。