正題

---

大意

兩棵樹，它們的相似值是它們留下最多的節(jié)點使它們的結(jié)構(gòu)相同。求相似值。

這兩顆樹就是結(jié)構(gòu)相同的，相似值是8。

---

解題思路

就是樹形dp。可以用f[i][j]f[i][j]表示樹1的第ii號節(jié)點和它的子樹與樹2的jj號節(jié)點與它的子樹的相似值，然后每個葉子節(jié)點的相似值就是1，然后每兩個非子節(jié)點的相似值就是它們的子節(jié)點之間相互匹配的最大價值，由于數(shù)據(jù)較小所以我們可以O(5!)O(5!)暴力枚舉，時間復(fù)雜度O(n2×5!)O(n2×5!)。

---

代碼

#include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define MN 1001 using namespace std; struct node{int to,next; }a1[MN],a2[MN]; vector<int> s1[MN],s2[MN]; bool v[MN]; int f[MN][MN],n,x,y,m; void zdfs(int k,int sum) {if (k>=s1[x].size()){f[x][y]=max(f[x][y],sum);return;}zdfs(k+1,sum);bool pd=false;for (int i=0;i<s2[y].size();i++)if (!v[i]){pd=true;v[i]=true;//標(biāo)記zdfs(k+1,sum+f[s1[x][k]][s2[y][i]]);//搜索下一個v[i]=false;//回溯}if (pd) f[x][y]=max(f[x][y],sum); } void dfs(int k) {if (!s1[k].size()){for (int i=1;i<=m;i++)f[k][i]=1;//葉子節(jié)點相似值為1return;}for (int i=0;i<s1[k].size();i++)dfs(s1[k][i]);//dp子節(jié)點for (int i=1;i<=m;i++){if (!s2[i].size()) f[k][i]=1;//對面為葉子節(jié)點也是相似值為1else{x=k;y=i;zdfs(0,0);//暴力匹配f[k][i]++;//算上自己}} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<n;i++){scanf("%d%d",&x,&y);s1[x].push_back(y);}for (int i=1;i<m;i++){scanf("%d%d",&x,&y);s2[x].push_back(y);}dfs(1);//dpprintf("%d",f[1][1]); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的jzoj4272-序章-弗兰德的秘密【树形dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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