【CF1280】C. Jeremy Bearimy（贪心）

本文主要是介绍【CF1280】C. Jeremy Bearimy（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://codeforc.es/contest/1280/problem/C

分析

**最小值：**根据贪心策略，我们每一条边用的次数要尽量少，如果一条边的两边都有偶数个点，那么这条边肯定不用；相反的，如果一条边两边都有奇数个点，那么这条边不得不用，因为奇数个点不足以都凑成对，必须跨边去借点。

**最大值：**类似于最小值的思路，每一条边我们要用尽量多的次数，如果一条边的两边分别有$n$，$2k-n$个点，那么这条边最多可以被用到$min(n,2k-n)$次，这样我们就可以找到最大值。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 300007;
int t,k,n;
struct node{int v,w;
};
vector<node> g[N];
int vis[N], sum[N];
ll maxn,minn;void dfs(int x)
{vis[x] = 1;sum[x] = 1;for(int i=0;i<g[x].size();i++){int v = g[x][i].v, w = g[x][i].w;if(vis[v] == 1) continue;dfs(v);sum[x] += sum[v];if(sum[v] & 1) minn += w;maxn += 1ll * w * min(sum[v], n - sum[v]);}
}int main()
{scanf("%d",&t);while(t--){scanf("%d",&k);n = 2 * k;for(int i=1;i<=n;i++) g[i].clear(), vis[i] = 0;for(int i=1;i<=n-1;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u].push_back({v, w});g[v].push_back({u, w});}vis[1] = 1;minn = maxn = 0;dfs(1);printf("%lld %lld\n",minn, maxn);}return 0;
}

这篇关于【CF1280】C. Jeremy Bearimy（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---