牛客多校10 - Identical Trees(dp+二分图最小权匹配)

题目链接：点击查看

题目大意：给出两个同构树 tree1 和 tree2 ，问最少需要改变多少个结点的标号，可以使得这两棵树相同

题目分析：直接 dfs 维护 dp 就好了，dp[ i ][ j ] 表示 tree1 中点 i 的子树与 tree2 中点 j 的子树相同所需要的最小代价，如果点 i 的子树和点 j 的子树不同构的话，那么答案设置为无穷大，最后答案就是 dp[ rt1 ][ rt2 ] 了

二分图权匹配我用的是KM算法，随机数据的话时间复杂度为 n^3 ，极限数据会被卡到 n^4，不过这个题目应该没有卡KM

无穷大的话我设置的是 1e6，因为 1e6 * 500 <= 1e9 并且 500 * 500 <= 1e6 ，既不会爆 int，且大小也刚好合适

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=1000000;const int N=510;int n;int la[N],lb[N];//顶标bool visa[N],visb[N];//访问标记int maze[N][N];//边权int match[N];//右部点匹配了哪一个左部点int upd[N];bool dfs(int x) {visa[x]=true;//访问标记：x在交错树中for(int i=1;i<=n;i++){if(!visb[i]){if(la[x]+lb[i]-maze[x][i]==0)//相等子图{visb[i]=true;//访问标记：y在交错树中if(!match[i]||dfs(match[i])){match[i]=x;return true;}}elseupd[i]=min(upd[i],la[x]+lb[i]-maze[x][i]);}}return false; } int KM() {memset(match,0,sizeof(match));for(int i=1;i<=n;i++){la[i]=-inf;lb[i]=0;for(int j=1;j<=n;j++)la[i]=max(la[i],maze[i][j]);}for(int i=1;i<=n;i++){while(1)//直到左部点找到匹配{memset(visa,false,sizeof(visa));memset(visb,false,sizeof(visb));memset(upd,inf,sizeof(upd));if(dfs(i))break;int delta=inf;for(int j=1;j<=n;j++)if(!visb[j])delta=min(delta,upd[j]);for(int j=1;j<=n;j++)//修改顶标{if(visa[j])la[j]-=delta;if(visb[j])lb[j]+=delta;}}}int ans=0;for(int i=1;i<=n;i++)ans+=maze[match[i]][i];return ans; }vector<int>nodea[N],nodeb[N];int dp[N][N];//dp[i][j]:第一棵树中i的子树和第二棵树中j的子树匹配的最小修改次数(如果i和j的子树不同构,dp[i][j]=inf) void dfs(int x,int y) {if(nodea[x].size()!=nodeb[y].size())return;if(x!=y)dp[x][y]=1;elsedp[x][y]=0;if(nodea[x].empty())return;for(auto u:nodea[x])for(auto v:nodeb[y])dfs(u,v);n=nodea[x].size();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)maze[i][j]=-dp[nodea[x][i-1]][nodeb[y][j-1]];int temp=-KM();if(temp>=inf)dp[x][y]=inf;elsedp[x][y]+=temp; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,rta,rtb;scanf("%d",&n);for(int i=1;i<=n;i++){int fa;scanf("%d",&fa);if(fa==0)rta=i;elsenodea[fa].push_back(i);}for(int i=1;i<=n;i++){int fa;scanf("%d",&fa);if(fa==0)rtb=i;elsenodeb[fa].push_back(i);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=inf;dfs(rta,rtb);printf("%d\n",dp[rta][rtb]);return 0; }

 

总结

以上是生活随笔为你收集整理的牛客多校10 - Identical Trees(dp+二分图最小权匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。