SRM638Div2_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了SRM638Div2_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2620字，纯文字阅读大概需要4分钟。
内容图文
2333.。。 由于TC参赛数太少，加上不断的fst 我都降到div2了。
还好做完就回div1了。。
250
水题
500
水题。。
直接bfs扩展就行了
注意判重， 我还用康托展开了真是多此一举。。
1000
这题理解错题意了。。我说看别人代码怎么看着不对劲来着
不过还是非常容易的一道题
二进制枚举烧哪些叶子结点
然后对每种烧法
求最短路
求完最短路，枚举边
假设边的两个结点是u,v权值为w
就求最大的(dis[u]+dis[v]+w )/2就是烧完的时间
为啥这样呢
假设某边是最后被烧掉的，有两种情况
一种是u,v分别都是由别的结点传来的火烧过来的
一种是u被v传来的火烧过来的
第一种，不妨设dis[u] > dis[v]
答案就是( L-(dis[u] - dis[v]) ) / 2 + dis[u] = (dis[u] + dis[v] + L) / 2
第二种
dis[v] + L = dis[u]
那么同样dis[u] = (dis[v] + L + dis[u]) / 2
二者都可以用这个表示了
然后为了方便我们就不除以2了
struct node { int v, w; node () {} node (int _v, int _w) {v = _v; w = _w;}};vectorg[22];int ind[22], lea[22], pos[22], d[22], vis[22], q[1111];set s;class CandleTimerEasy{public: int differentTime(vector A, vector B, vector len) { int n = A.size() + 1; for(int i = 0; i < n; i++) g[i].clear(); memset(ind, 0, sizeof(ind)); for(int i = 0; i < n - 1; i++) { g[A[i]].push_back(node(B[i], len[i])); g[B[i]].push_back(node(A[i], len[i])); ++ind[A[i]]; ++ind[B[i]]; } s.clear(); int cnt = 0; memset(pos, -1, sizeof(pos)); for(int i = 0; i < n; i++) { if(ind[i] == 1) { lea[cnt] = i; pos[i] = cnt; cnt++; } } for(int sta = 1; sta < (1 << cnt); sta ++) { int h = 0, t = 0; for(int i = 0; i < n; i++) { d[i] = INF; vis[i] = 0; if(pos[i] != -1) { if(sta & (1 << pos[i])) { q[t++] = i; d[i] = 0; vis[i] = 1; } } } while(h < t) { int u = q[h++]; vis[u] = 0; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; int w = g[u][i].w; if(d[u] + w < d[v]) { d[v] = d[u] + w; if(!vis[v]) { q[t++] = v; vis[v] = 1; } } } } int mx = 0; for(int i = 0; i < n - 1; i++) mx = max(mx, d[A[i]] + d[B[i]] + len[i]); s.insert(mx); } return (int)s.size(); }}
内容总结
以上是互联网集市为您收集整理的SRM638Div2_html/css_WEB-ITnose全部内容，希望文章能够帮你解决SRM638Div2_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。