HDU-4705 Y(思维+dfs树)
2018-11-20 03:15:15来源:博客园 阅读 ()
Input
4 1 2 1 3 1 4
Output
1
题意:给你一颗树,选择一个三个点构成的集合,使得这三个点不在一条直线上(意思就是 从一个点出发,用一条不回头的线不能将这三个点连起来)问一共有多少个这样的集合
思路 :先求出一共有多少个集合,就是Cn3 (n-2)*(n-1)*n/6 ; 然后再求不符合条件的个数
求不符合条件的集合时 比如上图:先以2为中心然后在3中选一个,在4,5,1,6,7,8,9中选一个种类数就是1×7
然后在4中选一个,在5,1,6,7,8,9中选一个种类数是1×6;
依此递归求解;
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdio> 4 #include <vector> 5 #include <algorithm> 6 #include <cstring> 7 using namespace std; 8 typedef long long ll; 9 const int maxn=1e6+5; 10 ll n; 11 ll sizes[maxn],ans; 12 vector<int> v[maxn]; 13 ll cal(ll n,ll m) 14 { 15 return n*(n-1)*(n-2)/6; 16 } 17 void dfs(int x,int fa) 18 { 19 sizes[x]=1; 20 for(int i=0;i<v[x].size();i++) 21 { 22 int y=v[x][i]; 23 if(y!=fa) 24 { 25 dfs(y,x); 26 sizes[x]+=sizes[y]; 27 ans+=(sizes[y]*(n-sizes[x])); 28 } 30 } 31 } 32 int main() 33 { 34 int T; 35 36 while(~scanf("%lld",&n)) 37 { 38 ans=0; 39 memset(sizes,0,sizeof(sizes)); 40 for(int i=1;i<=n;i++)v[i].clear(); 41 for(int i=1;i<n;i++) 42 { 43 int L,K; 44 scanf("%d%d",&L,&K); 45 v[K].push_back(L); 46 v[L].push_back(K); 47 } 48 dfs(1,-1); 49 printf("%lld\n",cal(n,3)-ans); 50 } 51 52 53 return 0; 54 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 朋友(翻转树边权值比赛)——依然是思维 2020-04-12
- Emergency Evacuation(最短下车时间)———(思维) 2020-04-11
- poj3045 Cow Acrobats (思维,贪心) 2019-10-12
- 一道有意思的思维题 --- 排序、枚举 2019-10-08
- 牛客国庆集训day6 B Board (模拟标记思维或找规律或分块? 2018-10-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash