H题意：
给你一个n个节点n-1条无向边构成的树，每一个节点有一个权值wi，你需要把这棵树划分成k个子树，每一个子树的权值是这棵子树上所有节点权值之和。
你要输出这k棵子树的权值中那个最大的。你需要让输出的结果尽可能小
题解：
二分结果，重要的是判断这个二分的值是否满足题目要求
对于划分子树的选择，就选择子树中权值最大且又满足二分的答案的那个子树
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const long long Max = 1e14 + 10; int n, k, cnt, flag, head[maxn], num; ll w[maxn], sum[maxn]; struct Edge { int v, nex; } e[maxn << 2]; void add_edge(int x, int y) { e[cnt].v = y; e[cnt].nex = head[x]; head[x] = cnt++; } void dfs(int x, int fa, ll limit) { sum[x] = w[x]; for (int i = head[x]; ~i; i = e[i].nex) { if (!flag) return; int v = e[i].v; if (v != fa) { dfs(v, x, limit); sum[x] += sum[v]; } } if (!flag) return; if (sum[x] > limit) { vector<ll> vec; for (int i = head[x]; ~i; i = e[i].nex) { int v = e[i].v; if (v != fa) vec.push_back(sum[v]); } sort(vec.begin(), vec.end()); //int len=vec.size(); while (sum[x] > limit) { // sum[x]-=vec[len-1]; // num++; // vec.pop_back(); // len--; sum[x] -= vec.back(); vec.pop_back(); num++; } vec.clear(); } if (num > k - 1) //因为我们没有把vec清空，所以最后还需要num数量还需要加1 { flag = 0; return; } } bool check(ll x) { flag = 1; num = 0; dfs(1, 0, x); if (flag) return 1; else return 0; } int main() { int t, p = 0; scanf("%d", &t); while (t--) { cnt = 0; memset(head, -1, sizeof(head)); memset(sum, 0, sizeof(sum)); scanf("%d%d", &n, &k); for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); add_edge(x, y); add_edge(y, x); } ll l = 1, r = Max, mid, ans; for (int i = 1; i <= n; ++i) { scanf("%lld", &w[i]); l = max(l, w[i]); } while (l <= r) { mid = (l + r) >> 1; if (check(mid)) { r = mid - 1; ans = mid; } else { l = mid + 1; } } printf("Case #%d: %lld ", ++p, ans); } return 0; }
K题意：
给你一个由n个节点m条边构成的一个无向图。保证不会出现重边和自环。你需要给边染色，你需要保证给一些边染色之后，图里面不会出现一个奇数环且这个环的所有边都被染色了。问你最多能给多少边染色。
题解：
就是二分图的一个性质。
你把这n个点分成两个集合（这一点暴力枚举就可以了，毕竟n<=16），然后如果一条边的两个端点在一个集合就不给它染色，否则就染色
代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 10 + 10; const int INF = 0x3f3f3f3f; struct shudui { int x, y; } e[1000]; int main() { int t, p = 0; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { int x, y; scanf("%d%d", &x, &y); x -= 1; y -= 1; e[i].x = x; e[i].y = y; } int sum = 0; for (int i = 1; i < (1 << n); ++i) //for (int i = 7; i <= 7; ++i) { int res = 0; for (int j = 1; j <= m; ++j) { int x = e[j].x; int y = e[j].y; //printf("%d %d %d %d ", x, y, ((1 << x) & i), ((1 << y) & i)); if ((((1 << x) & i) > 0 && ((1 << y) & i) == 0) || (((1 << x) & i) == 0 && ((1 << y) & i) > 0)) { res++; } } // if (res == 5) // { // printf("%d*** ", i); // } sum = max(sum, res); } printf("Case #%d: %d ", ++p, sum); } return 0; }