第一次写省队难度题目的题解,心里也是有点激动的辣!!!
题意:给你m棵树,让你先简化一下每棵树(这乱搞一下),然后把不同构(同构的定义不知道的话就去百度一下吧。。)的所有简化树的节点数从小到大输出来。
题解:我们只要把每种不同构的树用不同的权值表示,这样这道题就迎刃而解了。那么如何表示这个权值呢?请教了一下金牌爷gonens,。我们可以用类似于拓扑排序的方法来计算这个权值。先把所有度为1的点放入队列中,令他们的权值都为1。然后一层一层往上搜,每次发现当前的这个点度变为1时,就计算一下他的权值,把他儿子(注意:这里的儿子是有限制的:已经算好权值且和他不在同一层)的权值从小到大排个序,然后第一个数乘以A1,第二个数乘以A2,…,第n个数乘以An,A为自己定一个质数,然后加起来取模一个P就好了。至此,此题就顺利解决了。
不要问我一开始为什么T了,边表数组没开两倍啊。
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include <iostream> #define mod 1000000007 using namespace std; typedef long long ll; struct node{ll hash;int num;}p[25]; int n,m,u,v,edgenum,num; ll mi[10010]; int vet[20010],next[20010],head[20010],flag[10010],fa[10010],d[10010],du[10010],id[10010],q[10010],dep[10010],P[25]; ll f[10010],a[10010]; void add(int u,int v) { edgenum++; vet[edgenum]=v; next[edgenum]=head[u]; head[u]=edgenum; } void dfs(int u,int pre) { flag[u]=1; fa[u]=pre; if (d[u]!=2) id[u]=++num;else id[u]=pre; for (int e=head[u];e>0;e=next[e]) { int v=vet[e]; if (!flag[v]) dfs(v,id[u]); } } ll calc(int u) { int cnt=0; for (int e=head[u];e;e=next[e]) { int v=vet[e]; if (flag[v]&&dep[v]!=dep[u]) a[cnt++]=f[v]; } sort(a,a+cnt); ll ans=0; for (int i=0;i<cnt;i++) ans=(ans+mi[i]*a[i]%mod)%mod; return ans; } bool cmp1(const node x,const node y){return x.hash<y.hash;} int main() { scanf("%d",&m); mi[0]=1; for (int i=1;i<=10000;i++) mi[i]=mi[i-1]*10003%mod; for (int k=1;k<=m;k++) { scanf("%d",&n); memset(d,0,sizeof(d)); memset(head,0,sizeof(head)); edgenum=0; for (int i=1;i<n;i++) { scanf("%d%d",&u,&v); d[u]++;d[v]++; add(u,v);add(v,u); } num=0; memset(flag,0,sizeof(flag)); memset(fa,0,sizeof(fa)); for (int i=1;i<=n;i++) if (d[i]!=2){dfs(i,0);break;} memset(head,0,sizeof(head)); memset(du,0,sizeof(du)); edgenum=0; for (int i=1;i<=n;i++) if (id[i]!=fa[i]&&fa[i]!=0){add(id[i],fa[i]);add(fa[i],id[i]);du[id[i]]++;du[fa[i]]++;} int p1=0,p2=0; memset(dep,0,sizeof(dep)); memset(flag,0,sizeof(flag)); for (int i=1;i<=num;i++) if (du[i]==1){q[++p2]=i;dep[i]=0;flag[i]=1;f[i]=1;} while (p1<p2) { u=q[++p1]; for (int e=head[u];e;e=next[e]) { int v=vet[e]; if (!flag[v]) { du[v]--; if (du[v]==1) { flag[v]=1; dep[v]=dep[u]+1; q[++p2]=v; f[v]=calc(v); } } } } sort(f+1,f+num+1); for (int i=1;i<=num;i++) p[k].hash=(p[k].hash+f[i]*mi[i-1]%mod)%mod; p[k].num=num; } sort(p+1,p+m+1,cmp1); n=1; P[1]=p[1].num; for (int i=2;i<=m;i++) if (p[i].hash!=p[i-1].hash) P[++n]=p[i].num; printf("%d\n",n); sort(P+1,P+n+1); for (int i=1;i<n;i++) printf("%d ",P[i]); printf("%d\n",P[n]); }
2015年11月25日 02:08
%%%%%%%%%%%%%%%%%%%%%%%%%%%双国一叶爷爷