首页 > 代码库 > BZOJ3522: [Poi2014]Hotel
BZOJ3522: [Poi2014]Hotel
3522: [Poi2014]Hotel
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 195 Solved: 85
[Submit][Status]
Description
有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意？
Input
第一行一个数n。
接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。
Output
让吉丽满意的方案数。
Sample Input
7
1 2
5 7
2 5
2 3
5 6
4 5
1 2
5 7
2 5
2 3
5 6
4 5
Sample Output
5
HINT
【样例解释】
{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}
【数据范围】
n≤5000
Source
By Dzy
题解：
这题搞了好久时间。。。
直接贴代码吧，我已经记住这道题了。。。
代码：
View Code
这题搞了好久时间。。。
直接贴代码吧，我已经记住这道题了。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 5000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,tot,head[maxn]; 61 ll f[maxn][3],s[maxn]; 62 struct edge{int go,next;}e[2*maxn]; 63 inline void insert(int x,int y) 64 { 65 e[++tot]=(edge){y,head[x]};head[x]=tot; 66 e[++tot]=(edge){x,head[y]};head[y]=tot; 67 } 68 inline void dfs(int x,int fa,int dep) 69 { 70 s[dep]++; 71 for(int i=head[x];i;i=e[i].next) 72 if(e[i].go!=fa)dfs(e[i].go,x,dep+1); 73 } 74 75 int main() 76 77 { 78 79 freopen("input.txt","r",stdin); 80 81 freopen("output.txt","w",stdout); 82 83 n=read(); 84 for1(i,n-1)insert(read(),read()); 85 ll ans=0; 86 for1(x,n) 87 { 88 for(int i=head[x];i;i=e[i].next) 89 { 90 dfs(e[i].go,x,1); 91 for1(j,n) 92 if(s[j]) 93 { 94 f[j][2]+=f[j][1]*s[j]; 95 f[j][1]+=f[j][0]*s[j]; 96 f[j][0]+=s[j]; 97 s[j]=0; 98 } 99 else break;100 }101 for1(j,n)if(f[j][0])ans+=f[j][2],f[j][2]=f[j][1]=f[j][0]=0;else break;102 }103 printf("%lld\n",ans);104 105 return 0;106 107 }
比较明显的组合计数用数学来搞比较好，稍微复杂一点的不如用递推式来递推。
UPD:还是写一下题解吧。。。
我们枚举每个点做根，那么合法的方案就是在不同的子树中取出3个dep相同的节点的方案数，每dfs一棵子树，我们就用它的信息来更新ans，注意信息用了就要清空。
BZOJ3522: [Poi2014]Hotel
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。