LTC 男人八题之一,解题报告见09看论文。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int const N= 10010, inf= 0x7fffffff;
int n, k, cnt, tot, root, size, nchild, first, last, pre, ans;
int Fnum;
struct Edge{
int adj, wt;
Edge* next;
}tb[N<<1];
Edge* mat[N];
int dist[N], flag[N], que[N], vis[N], num[N];
void inline add( int u, int v, int d ){
++cnt;
tb[cnt].adj= v; tb[cnt].wt= d;
tb[cnt].next= mat[u]; mat[u]= tb+ cnt;
++cnt;
tb[cnt].adj= u; tb[cnt].wt= d;
tb[cnt].next= mat[v]; mat[v]= tb+ cnt;
}
int selectRoot( int rt ){
flag[rt]= Fnum;
int tmp= 0, sum= 0;
for( Edge* p= mat[rt]; p; p= p->next ){
int v= p->adj;
if( vis[v]== 0 && flag[v]!= Fnum ){
int s= selectRoot( v );
if( s> tmp ) tmp= s;
sum+= s;
}
}
if( nchild- 1- sum> tmp ) tmp= nchild- 1- sum;
if( tmp< size ){ size= tmp; root= rt; }
return sum+ 1;
}
int inline getCount( int first, int last ){
sort( dist+ first, dist+ last+ 1 );
int head= first, tail= last, ret= 0;
while( first< last ){
if( dist[first]+ dist[last]<= k ) ret+= last- first++;
else last--;
}
return ret;
}
int dfs( int rt, int len ){
flag[rt]= Fnum; dist[++last]= len;
int sum= 0;
for( Edge* p= mat[rt]; p; p= p->next )
if( !vis[p->adj] && flag[p->adj]!= Fnum ){
int v= p->adj, wt= p->wt;
sum+= dfs( v, len+ wt );
}
num[rt]= sum+ 1;
return sum+ 1;
}
void solve( int rt ){
pre= 1;
for( Edge* p= mat[rt]; p; p= p->next )
if( !vis[p->adj] && flag[p->adj]!= Fnum ){
int v= p->adj, wt= p->wt;
dfs( v, wt );
ans-= getCount( pre, last );
pre= last+ 1;
}
}
int main(){
while( scanf("%d%d",&n,&k)!= EOF ){
if( n== 0 && k== 0 ) return 0;
for( int i= 0; i<= n; ++i ) mat[i]= 0, flag[i]= 0, vis[i]= 0;
cnt= -1; tot= -1;
int u, v, d;
for( int i= 1; i< n; ++i ){
scanf("%d%d%d", &u,&v,&d );
add( u, v, d );
}
int head= 0, tail= 0; que[0]= 1;
nchild= n; ans= 0; Fnum= 0; num[1]= n;
while( head<= tail ){
int now= que[head++]; nchild= num[now]; Fnum++;
size= 0x7fffffff; selectRoot( now ); vis[root]= 1;
for( Edge*p= mat[root]; p; p= p->next )
if( !vis[p->adj] ) que[++tail]= p->adj;
first= pre= 1; last= 0; Fnum++;
solve( root ); dist[++last]= 0;
ans+= getCount( first, last );
}
printf("%d\n", ans );
}
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
用Java代码实现POJ(PKU)上题2494!
acm 1001 到1009代码,已通过验证
O(nlogn)凸包问题 poj2187
acm pku poj 1000 1001 1002 1003 1201
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
花了老长时间琢磨。。终于还是过了,长了很多经验,写的简单易懂。。
pku 123 题目代码 pku acm poj
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/ 及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计...
poi3252,北大acm里面的题目代码。
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
PKU,POJ共301题源代码。1001 1002 1003 1004 1005 1006 1007 1008 1011 1012 1013 1014 1015 1017 1018 1019 1028 1032 1042 1046 1050 1061 1065
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
#include #include using namespace std; int main() { double v,d; while(scanf("%lf%lf",&d,&v)==2 && d!=0.0 ) printf("%.3lf\n",pow((d*d*d-6*v/3.1415926536),1.0/3)); return 0; }