• 周日. 6月 26th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

牛客多校 第六场 J Defend Your country

admin

11月 28, 2021

赛场上被兔子洞卡住了,没看这题

题意:给一张无向连通图,若一个连通块的点数为偶数,则贡献为点权和,否则为点权和的负数

问整张图删去若干边后的最大贡献。

解:因为一开始就是联通的,所以如果n是偶数,那不用删,直接输出

若是奇数,那么我们要不删的是割点,要不是非割点,割点删除后必须要剩下的连通块都是偶数,

因此在非割点和删除后都是偶数连通块的割点里面取个最小值删掉。

所以拿tarjan跑一遍就行

(题解老哥的tarjan写的真好看%%%

下附代码:

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll INF=0X3f3f3f3f3f3f3f3f;
 5 int n, m; // n:点数 m:边数
 6 int dfn[1000001], low[1000001], inde, res;
 7 int siz[1000005];
 8 int ok[1000005];
 9 ll a[1000005];
10 // dfn:记录每个点的时间戳
11 // low:能不经过父亲到达最小的编号,inde:时间戳,res:答案数量
12 bool flag[1000001]; // flag: 答案 vis:标记是否重复
13 vector<int> edge[1000001];       // 存图用的
14 void Tarjan(int u, int father)
15 {                             // u 当前点的编号,father 自己爸爸的编号       
16     low[u] = dfn[u] = ++inde; // 打上时间戳
17     siz[u] = 1;
18     int child = 0;            // 每一个点儿子数量
19     for (auto v : edge[u])
20     { // 访问这个点的所有邻居 (C++11)
21 
22         if (!dfn[v])
23         {                   
24             Tarjan(v, father);  
25             siz[u]+=siz[v];
26             if (siz[v]%2 && low[v]>=dfn[u]) ok[u]=0;              
27             low[u] = min(low[u], low[v]); 
28             if (father != u && low[v] >= dfn[u] ) 
29             {
30                 flag[u] = true;
31             }
32             else if (u==father) child++;
33         }
34         else 
35             low[u] =min(low[u], dfn[v]); 
36     }
37     if (father == u && child >= 2){ 
38         flag[u] = true;
39     }
40 }
41 int main()
42 {
43     int T;
44     scanf("%d",&T);
45     while (T--){
46         inde=0;
47         ll tot=0;
48         scanf("%d%d",&n,&m);
49         for (int i=1; i<=n; i++){
50             flag[i]=0,ok[i]=1,dfn[i]=0;
51             scanf("%d",&a[i]);
52             edge[i].clear();
53             tot+=a[i];
54         }
55         for (int i = 1; i <= m; i++)
56         { // 注意点是从 1 开始的
57             int x, y;
58             scanf("%d%d",&x,&y);
59             edge[x].push_back(y);
60             edge[y].push_back(x);
61         }             
62                     // 使用 vector 存图
63         if (n%2==0){
64             printf("%lld
",tot);
65             continue;
66         }
67         for (int i = 1; i <= n; i++) // 因为 Tarjan 图不一定连通
68             if (!dfn[i])
69             {
70                 inde = 0;     // 时间戳初始为 0
71                 Tarjan(i, i); // 从第 i 个点开始,父亲为自己
72             }
73         ll min1=INF,min2=INF;
74         for (int i=1; i<=n; i++){
75             if (flag[i]){
76                 if (ok[i]) min1=min(min1,a[i]);
77             }
78             else min2=min(min2,a[i]);
79         }
80         printf("%lld
",tot-2*min(min1,min2));
81     }
82     return 0;
83 }

View Code

发表评论

您的电子邮箱地址不会被公开。