【2018】 CSP - S 题解
T3
暴力分(55 分)
求树的直径$(20分)+$ 菊花图 $[sort](15分)+$ 一条链 $[二分+贪心](20分)$
正解
二分 $k$ 后,由贪心知,如果有一棵根为 $u$ 的子树,我们尽量在子树内配对出长大于等于 $k$ 的点是最优的,
这是因为,一个赛道不建在子树内,就只有一条出边,多配对一个显然 $>=$ 让延伸出子树的边更大。
这种时限卡的比较紧的题最好不用 $STL$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, cnt, up;
int h[N], w[N], e[N], ne[N], idx;
multiset<int> s[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u, int father, int k)
{
s[u].clear();
int val = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == father) continue;
val = dfs(j, u, k) + w[i];
if (val >= k) cnt ++;
else s[u].insert(val);
}
int Max = 0;
while (!s[u].empty())
{
if (s[u].size() == 1)
{
return max(Max, *s[u].begin());
}
multiset<int>::iterator it = s[u].lower_bound(k - *s[u].begin());
if (it == s[u].end())
{
Max = max(Max, *s[u].begin());
s[u].erase(s[u].find(*s[u].begin()));
}
else
{
cnt ++;
s[u].erase(s[u].find(*it));
s[u].erase(s[u].find(*s[u].begin()));
}
}
return Max;
}
bool check(int k)
{
cnt = 0;
dfs(1, -1, k);
return cnt >= m;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
up += c;
}
int l = 0, r = up;
while (l < r) // 单调递减
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d", l);
}
T4
枚举环的断点,当且仅当图还连通且字典序最小时为答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef pair<int, int> PII;
int n, m, state, cnt, del_u, del_v;
vector<int> e[N];
PII edge[N];
bool st[N];
vector<int> path(N), ans(N, N);
bool dfs(int u) // 用bool是为了及时返回
{
if (!state)
{
if (ans[cnt] < u) return true;
if (ans[cnt] > u) state = 1;
}
st[u] = true;
path[cnt ++ ] = u;
for (int i = 0; i < e[u].size(); i ++ )
{
int v = e[u][i];
if (!st[v] && !(v == del_u && u == del_v) && !(v == del_v && u == del_u))
{
if (dfs(v)) return true;
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b);
e[b].push_back(a);
edge[i] = {a, b};
}
for (int i = 1; i <= n; i ++ ) sort(e[i].begin(), e[i].end());
if (m == n-1)
{
dfs(1);
if (cnt == n) ans = path;
}
else
{
for (int i = 1; i <= m; i ++ )
{
del_u = edge[i].first, del_v = edge[i].second;
memset(st, false, sizeof st);
state = cnt = 0; dfs(1);
if (cnt == n) ans = path;
}
}
for (int i = 0; i < n; i ++ ) printf("%d ", ans[i]);
}