链接

B

这题有很多做法，并查集是比较简单的解法。
可以将数字细分到每一位，一旦某一位的数确定了，那么其他数字的该位也能确定，将一个数按照某一位取0还是取1分成两种状态，然后用并查集判断合法性，如果合法的话就让一个集合中最多的那种状态取0即可。
这一题会卡常数，写得不好有可能会TLE。

#include <algorithm>
#include <cstdio>
const int N = 2e5 + 5;
using namespace std;
int fa[N], u[N], v[N], w[N], sz1[N], sz2[N]; //sz1和sz2分别记录一个集合中两种状态的数量
int Find(int x)
{
if (fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
void init(int n)
{
for (int i = n; i >= 0; i--)
{
fa[i] = i, sz1[i] = sz2[i] = 0;
fa[i + n] = i + n, sz1[i + n] = sz2[i + n] = 0;
}
}
signed main()
{
int n, m;
long long ans = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d%d", &u[i], &v[i], &w[i]);
for (int i = 0; i <= 30; i++)
{
init(n);
int fu1, fv1, fu2, fv2, f1, f2, bit = 1 << i;
bool possible = 1;
for (int j = 0; j < m; j++)
{
fu1 = Find(u[j]);
fu2 = Find(u[j] + n);
fv1 = Find(v[j]);
fv2 = Find(v[j] + n);
if (w[j] & bit)
{
fa[fu1] = fa[fv2];
fa[fu2] = fa[fv1];
}
else
{
fa[fu1] = fa[fv1];
fa[fu2] = fa[fv2];
}
}
for (int j = 1; j <= n; j++)
{
f1 = Find(j);
f2 = Find(j + n);
if (f1 == f2) //一个位既是1又是0，出现矛盾，直接退出
{
possible = 0;
break;
}
sz1[f1]++;
sz2[f2]++;
}
if (possible)
{
for (int j = 1; j <= n; j++)
{
//将每个集合中状态少的都取1，由于算了两次，在最后输出的时候要除2
ans += (long long)min(sz1[j], sz2[j]) * bit;
ans += (long long)min(sz1[j + n], sz2[j + n]) * bit;
}
}
else
{
ans = -2;
break;
}
}
printf("%lld", ans / 2);
return 0;
}

H

题目的意思是给定一张图，将相邻的两条边（共享一个点）选出，求最大的边权和。
题目的思路很简单，如果边数是偶数，全部选出就好了，如果是奇数，要选出一条最小的非割边，或者是最小的割边，并且这条割边两侧连的边数都是偶数（如果不是偶数的话选择了这条边就会多出两条不能选择的边，势必不是最优答案）。
因此用tarjan算法求出割边，以及每条割边两侧连的边数。也算是复习了一遍tarjan算法求割边了。
这题需要注意的是一个点连接的边数要放到具体的边来判定，一个点可能在多条边上，在不同的边上时这个点连接的边数是不一样的，因此代码中的es数组存的是下标为i的边两端连接的边数。比如es1[i]是e[i]这条边一端的边数,es2[i]是e[i]这条边另一端的边数。

#include <bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))
const int inf = 0x7fffffff;
const int N = 4e5 + 5;
using namespace std;
struct edge
{
int to, next, len;
} e[N];
int head[N], cnt = 1;
int bridge[N];
int dfn[N], low[N], de[N], es1[N], es2[N], tot = 0, m, n;
void addEdge(int u, int v, int w)
{
e[++cnt].to = v;
e[cnt].len = w;
e[cnt].next = head[u];
head[u] = cnt;
}
void tarjan(int u, int pre)
{
dfn[u] = low[u] = ++tot;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
{
//如果这是割边就要计算两端连接的边数
es1[i] = es1[i ^ 1] = de[v] / 2;//一个点的度数存在重复计算，因此要除2（这个不太好理解，建议自己模拟一遍）
es2[i] = es2[i ^ 1] = m - es1[i] - 1;//总边数减去另一端的边数再减去当前这条边
bridge[i] = bridge[i ^ 1] = 1;
}
de[u] += de[v];
}
else if (v != pre)
low[u] = min(low[u], dfn[v]);
}
}
int main()
{
mem(head, 0), mem(dfn, 0), mem(low, 0), mem(de, 0), mem(bridge, 0);
int u, v, w;
long long ans = 0;
int mine = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
de[u]++;
de[v]++;
addEdge(u, v, w);
addEdge(v, u, w);
ans += w;
}
if (m & 1)
{
mine = inf;
tarjan(1, 0);
for (int i = 1; i <= n; i++)
{
for (int j = head[i]; j; j = e[j].next)
{
if (bridge[j] == 0)
mine = min(mine, e[j].len);
else if (es1[j] % 2 == 0 && es2[j] % 2 == 0)
mine = min(mine, e[j].len);
}
}
}
printf("%lld", ans - mine);
return 0;
}

最后

以上就是苹果手套为你收集整理的2021 ICPC沈阳 B H题题解BH的全部内容，希望文章能够帮你解决2021 ICPC沈阳 B H题题解BH所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。