锐客网

  1. 首页 > 睿知 > it技术 > >

CF 660 C. Uncle Bogdan and Country Happiness

IT知识countHappinesscountry

怀抱观古今，寝食展戏谑。这篇文章主要讲述CF 660 C. Uncle Bogdan and Country Happiness相关的知识，希望能为你提供帮助。
CF 660 C. Uncle Bogdan and Country Happiness 题目链接【CF 660 C. Uncle Bogdan and Country Happiness】C. Uncle Bogdan and Country Happiness
题目概述初始时每个人都在标号为1的城市,然后回到每个人各自的城市,选择从起点到终点的最短路径,相邻城市之间的距离一样,每个人在进入一个城市时可以改变他的心情,从Good变为Bad,但是不可以从Bad变成Good,每个人进入一个城市时他的心情会影响这个城市的幸福指数,如果是Good那么指数加一否则减一,在城市里面心情是不会改变的,现在给出一种城市幸福指数的可能性,计算有没有可能得到这种幸福指数格局?
数据规模:
[1leq t leq 10000, 1leq n leq 10^5, 0leq mleq 10^9leq p_i leq m, sum_{i=1}^{n}p_i = m-10^9 leq h_i leq 10^9 , i=1,2,3dots,n. ]
思路设经过结点v的人有a个,其中好心情的有g个,坏心情的有b个,从而可以得到:
[a = g+b, h = g-b; ]
两式相加得到(g=frac{a+h}{2}),所以((a+h)\%2=0)是第一个约束条件.
有上面的式子同事可以得到另外一个明显的约束条件(0 leq g leq a),最后由于允许路上允许从高兴变成不高兴,所以在结点v的幸福指数一定不会从结点v到终点后面路径上结点的幸福指数(g_{next})之和低的.从而得到上面这三个约束条件.
这里面的主要的问题就是计算每个结点的a和g,这些有两部分组成,一部分是它自身的(p)和(frac{a+h}{2}),另外一部分是经过这个结点才能得达的结点,也就是它的后继,要先计算出后继,才能得到这个结点,然后这个结点就算出的作为上一层的后继的结果,对于那些没有后继的结点,就他的a和g仅由前面那一部分组成,计算后直接返回.最终的计算过程是自顶向下分解,然后求解出不可分解的部分后返回到上一层,处理上一层,然后继续返回,可以用递归方便的模拟这个过程,携程程序就是一个简单的dfs.
代码

/* * @Author: Shuo Yang * @Date: 2020-07-30 21:47:50 * @LastEditors: Shuo Yang * @LastEditTime: 2020-07-31 22:16:58 * @FilePath: /Code/CF/660/C.cpp */ #include< bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+5; vector< int> buf[N]; int a[N],p[N],h[N],g[N]; bool flag = true; void dfs(int v, int ancestor = -1) { a[v] = p[v]; int sum = 0; for(auto to: buf[v]){ if(to == ancestor) continue; dfs(to, v); a[v] += a[to]; sum += g[to]; } g[v] = (a[v]+h[v])/2; if((a[v]+h[v])%2 != 0) flag = false; if(g[v] < 0 || g[v] > a[v]) flag = false; if( sum > g[v]) flag = false; }int main(int argc, const char** argv) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin> > t; while(t--){ int n,m; cin> > n> > m; for(int i = 1; i < = n; ++i) cin> > p[i]; for(int i = 1; i < = n; ++i) cin> > h[i]; for(int i = 0; i < n-1; ++i){ int a,b; cin> > a> > b; buf[a].push_back(b); buf[b].push_back(a); } dfs(1); if( flag ) cout< < " YES" < < endl; else cout< < " NO" < < endl; flag = true; for(int i = 1; i < =n; ++i) buf[i].clear(); } return 0; }

其它

    推荐阅读


    上一篇：2mapper.xml将jdbcType写错为javaType

    下一篇：出现Error:Execution failed for task &#39;:app:preDebugAndroidTestBuild&#39;. 的解决办法