牛客练习赛27
github博客地址
A 纸牌
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << (n + 1) / 2 << endl;
return 0;
}
C 水图
只有一条路不用回来，其他都要回到开始点；所以，除了最长路，都要走来回，求最长路，就是最优解
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<int, int>> mp[5005];
ll ans;
bool vis[5005];
void dfs(int x, ll len)
{
if (mp[x].size() == 1 && vis[mp[x][0].first])
{
ans = max(ans, len);
return;
}
for (auto &i : mp[x])
if (!vis[i.first])
{
vis[i.first] = 1;
dfs(i.first, len + i.second);
}
}
int main()
{
int n, x;
cin >> n >> x;
ll sum = 0;
for (int i = 0; i < n - 1; i++)
{
int u, v, len;
cin >> u >> v >> len;
mp[u].push_back({v, len});
mp[v].push_back({u, len});
sum += len;
}
dfs(x, 0);
cout << sum * 2 - ans << endl;
return 0;
}
