首页 > 代码库 > 【NOI2011】【P1308】道路修建
【NOI2011】【P1308】道路修建
这题也太水了吧，为什么不是我这届的NOI(╯‵□′)╯︵┻━┻
原题：
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家 之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿 意修建恰好 n – 1 条双向道路。
每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4 个国家，如果该道路长度为 1，则费用为 1×|2 – 4|=2。图中圆圈里的数字表示国 家的编号。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建
费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计 算出所需要的费用。请你帮助国王们设计一个这样的软件
n<=1000000,ci<=1000000
刚开始看错题了，以为是给出任意两个国家的距离，然后求生成树……
但是树直接给出来了，直接求值即可不用维护最优值，就是个模拟么……
所以这道题应该算是树形递推而不是树归
先随便挑一个点搞树，稍加观察即可发现每个点和它爹之间连的边的权值就是|n-size[x]-size[x]|*value[x]（value[x]表示x和爹之间连边的长度）
然后就是求size
数据很大所以dfs会炸掉（Linux或者手动开栈不会炸？），所以使用bfs
先dfs一遍，把树建起来，然后倒着把队列遍历一遍，因为bfs是一层一层推得，所以反遍历队列就保证先到儿子，在到爹，然后就可以更新了
最后从2-n根据上面的公式↑求值累加即可（我把根节点设为1，根节点不用更新因为根节点没爹）
注意会炸int，如果乘法运算的结果会炸int的话乘的两个数必须至少有一个是longlong，这里把求绝对值函数的返回值设为longlong是一个不错的选择
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int read(){int z=0,mark=1; char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1; ch=getchar();} 9 while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘; ch=getchar();}10 return z*mark;11 }12 inline long long jue(long long x,long long y){return (x>y)?x-y:y-x;}//注意绝对值也要longlong13 struct ddd{int next,y,value;}e[2100000];int LINK[1100000],ltop=0;14 inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=http://www.mamicode.com/z;}15 struct dcd{int child,brother,father,value,size;}tree[1100000];16 inline void insert_tree(int x,int y,int z){tree[y].brother=tree[x].child;tree[x].child=y;tree[y].father=x;tree[y].value=http://www.mamicode.com/z;}17 int n;18 int dui[1100000],tou=0;19 void get_tree(){20 dui[tou=1]=1; tree[1].father=tree[1].value=http://www.mamicode.com/0;21 for(int k=1;k<=tou;k++)22 for(int i=LINK[dui[k]];i;i=e[i].next)if(e[i].y!=tree[dui[k]].father){23 insert_tree(dui[k],e[i].y,e[i].value);24 dui[++tou]=e[i].y;25 }26 for(int k=tou;k>=1;k--){27 tree[dui[k]].size=1;28 for(int i=LINK[dui[k]];i;i=e[i].next)if(e[i].y!=tree[dui[k]].father)29 tree[dui[k]].size+=tree[e[i].y].size;30 }31 }32 int main(){//freopen("ddd.in","r",stdin);33 cin>>n;34 int _left,_right,_value;35 for(int i=1;i<n;i++){36 _left=read(); _right=read(); _value=http://www.mamicode.com/read();37 insert(_left,_right,_value); insert(_right,_left,_value);38 }39 get_tree();40 long long ans=0;41 for(int i=2;i<=n;i++) ans+=jue(n-tree[i].size,tree[i].size)*tree[i].value;42 cout<<ans<<endl;43 return 0;44 }
【NOI2011】【P1308】道路修建