Codeforces 397 题目解答:给你一种树的边的合成方式,问你经过数次合成之后,能否变成线性结构,如果可以,求出这个结构最短的长度。
解题思路:按照拓扑排序的顺序,从度数为 1 的点开始 "删去",对于每一个节点用 set 保存从其他节点到这个节点的长度,如果有相同长度的就会自动 "合并"。所以,只有两种情况是满足条件的:
1. 有一个节点的 set 的大小是 2,其余的都是 1
2. 全部节点的 set 的大小都是 1
对于情况 1,答案就是 set 中两个数的和;对于情况 2,答案就是所有节点中 set 中的值最大的那个。
若答案为偶数,则根据题意,一定可以再进行一次合成,所以将答案除 2 直到为奇数即为最终答案。
- #include#include#include#include#include#include#include#include#include#include#include#include#include#include#define LL long long#define INF 0x3f3f3f3f#define PII pair#define fi first#define se second#define mp make_pair#define pb push_back#define lowbit(x)(x & ( - x)) using namespace std;
- const int N = 2e5 + 5;
- vectore[N];
- sets[N];
- queueq;
- bool vis[N];
- int d[N];
- int main() {
- int n;
- scanf("%d", &n);
- for (int i = 1; i2 || s[i].size() == 0) return 0 * puts("-1");
- else if (s[i].size() == 1) ans = max(ans, *s[i].begin());
- else cnt++,
- ans = max(ans, ( * s[i].begin()) + ( * s[i].rbegin()));
- if (cnt > 1) puts("-1");
- else {
- while (ans % 2 == 0) ans /= 2;
- printf("%d\n", ans);
- }
- return 0;
- }
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/02-21/17352509.html