题目概述
𝑛个点，𝑚条边的简单无向联通图，每个点一个权值 𝑎𝑖；
一个连通块的贡献： $(−1)^{块内点数} ⋅ ∑𝑎𝑖[点 𝑖 在该连通块内]$；
可任意删除一些边，求连通块贡献之和最大是多少。
数据范围
分析与解
首先拿到问题看似很复杂，但应该从简单的，或者极端的情况进行考虑。因为所有的点权都是正的，所以我们想让尽可能多的连通块都有偶数大小。
那么我们可以考虑假设所有的点都是可以取正点权来贡献答案，再考虑删掉哪些点使得原本是奇数大小的连通块变成偶数大小。
从贪心的角度考虑，我们需要找奇数点权的联通块中点权最小的点来删。但是需要判定一个问题，就是有可能删除的点是割点，因此我们需要Tarjan一波找到所有的割点，并判断这些割点连接的各连通块，如果删除了割点是否还能保证是偶数大小。
这个题其实结论转化为代码是直接的。关键在于结论的得来。也就是为什么只用删除一个点即可？
首先总点数为偶数的情况是显然的。我们来考虑总点数$n$为奇数的情况。
结论一：删除的节点一定是一些孤立点，且一共有奇数个。
反证法：如果删除的不是孤立点，而是奇数连通块，那么完全可以把这些$size \geq3$的连通块再删掉非割点以获得偶联通块增加答案。另一方面，如果孤立点一共有偶数个，则考虑删掉孤立点剩下的都是偶连通块，所以总点数为偶数，矛盾。
（下面的结论我暂时没明白）
结论二：假设孤立点的个数大于等于3，则答案必为原图割点，且剩下的奇数连通块需要再次进行找割点的操作。
首先，这些点一定都是原图的割点。否则，在原图上存在一个非割点，则将其割去，分成一个孤立点和一个偶数的连通块，答案更大。
现在如果在原图中把这些孤立点单独割去，那么剩下的连通块中一定存在至少两个奇数连通块（奇+奇=偶）。否则，可以仅需要单独割掉其中一个，答案会更优（原图总点数奇数=奇point+偶remain）。
（一个例子：假设原图组成为 偶-割-偶-割-偶-割-偶，单独割点最左或者最右的割点，其左右两个连通块点数都是偶数，比起把三个割点全部割掉答案更优。）
而由于至少两个连通块都是奇数个点，于是还需要在里面继续找割点并重复上面的操作。
结论三：答案仅会删除一个点
接下来，我们将割下来的孤立点放在点双树上，建立一棵虚树（不知道什么是点双树可以搜索圆方树，两者差不多是同一个东西），那么由于割点至少在两个方向上都有其他割点，但按照上述过程，存在孤立点必为叶子，即不可能在两个方向上都有其他割点。否则，这棵树就存在一个环。
一棵树怎么可能有环呢？假设不成立！
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 1000100
int n,m;
int a[MAXN];
struct node {
int v;
node *nnext;
} pool[MAXN<<1],*h[MAXN<<1];
int cnt=-1;
void addedge(int u,int v) {
node *p=&pool[++cnt];
p->v=v,p->nnext=h[u],h[u]=p;
node *q=&pool[++cnt];
q->v=u,q->nnext=h[v],h[v]=q;
}
int dfn[MAXN],low[MAXN],ind,siz[MAXN];
bool is_cut[MAXN],ok[MAXN];
void Tarjan(int u,int fa) {
int v,son=0;
low[u]=dfn[u]=++ind;
siz[u]=1;
for(node *p=h[u]; p; p=p->nnext) {
v=p->v;
if(v==fa)continue;
if(!dfn[v]) {
Tarjan(v,u);
siz[u]+=siz[v];
if(u==fa)son++;
if((siz[v]&1) && low[v] >= dfn[u])ok[u]=false;
low[u]=min(low[u],low[v]);
if(u!=fa && low[v]>=dfn[u])is_cut[u]=true;
} else
low[u]=min(low[u],dfn[v]);
}
if(u==fa && son > 1)is_cut[u]=true;
}
int mmin,now_size;
bool vis[MAXN];
void dfs(int u) {
int v;
vis[u]=true;
now_size++;
if((!is_cut[u] || (is_cut[u] && ok[u])) && a[u] < mmin)mmin=a[u];
for(node *p=h[u]; p; p=p->nnext) {
v=p->v;
if(!vis[v])
dfs(v);
}
}
void solve() {
int u,v;
LL ans=0;
n=mread(),m=mread();
for(int i=1; i<=n; i++) {
a[i]=mread();
ans+=a[i];
}
for(int i=1; i<=m; i++) {
u=mread(),v=mread();
addedge(u,v);
}
for(int i=1; i<=n; i++)ok[i]=true;
for(int i=1; i<=n; i++)
if(!dfn[i])
Tarjan(i,i);
for(int i=1; i<=n; i++)
if(!vis[i]) {
mmin=0x3f3f3f3f;
now_size=0;
dfs(i);
if(now_size & 1)
ans-=2ll*mmin;
}
printf("%lld\n",ans);
for(int i=0; i<=cnt; i++)pool[i].v=0,pool[i].nnext=NULL;
for(int i=1; i<=n; i++) {
h[i]=NULL;
dfn[i]=low[i]=vis[i]=siz[i]=0;
is_cut[i]=ok[i]=false;
}
ind=0;
cnt=-1;
}
int main() {
int kase;
kase=mread();
while(kase--) {
solve();
}
return 0;
}
|