补题情况

题目	蒋贤蒙	王赵安	王智彪
A	0	0	0
B	0	0	0
C	0	0	0
D	0	0	0
E	0	0	0
G	0	0	0
J	2	0	0
K	0	0	0

题解

J. Defend Your Country

题意

给定 $n$ 个点 $m$ 条边的连通图，要求删去任意条边，最大化图的点权和。

其中第 $i$ 个点的点权的绝对值为 $a_i$，如果该点所在连通块大小为偶数则权值为正，否则为负。

题解

不难发现如果 $n$ 为偶数则不需要任何删边。

如果 $n$ 为奇数，如果最优解中存在一个大小不为 $1$ 的奇连通块，任取该连通块的一个点删去所有相关连边一定不会使得答案变劣。

因此不妨考虑强制删一个点，如果这个点不是割点，显然删除该点后不需要额外删点，统计此时的答案。

如果这个点是割点，则需要考虑删去这个点得到的剩余连通分量，如果每个连通分量大小都是偶数，显然也不需要额外删点。

否则，删去该点会导致剩余连通分量的原割点不变，同时增加新割点，而且需要删去的点数也增加，一定使得答案变劣，因此不考虑。

至于维护删除割点后的其他连通分量奇偶性可以在跑 $\text{dfs}$ 树时顺便维护子树大小，根据子树奇偶性判断。

特别注意即使 $u$ 是割点，删除 $u$ 也不能保证 $u$ 的每个子树都构成独立连通分量。

事实上如果 $\text{low[v]}<\text{dfn}[u]$ 则说明 $v$ 和 $u$ 的祖先结点属于同一个点双连通分量，不要重复判定。比赛的时候就这里假了，长了个教训。

时间复杂度 $O(n+m)$。

查看代码

const int MAXN=1e6+5,MAXM=2e6+5,Inf=1e9;
struct Edge{
	int to,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
int low[MAXN],dfn[MAXN],sz[MAXN],dfs_t;
bool iscut[MAXN],fib[MAXN];
void dfs(int u,int fa){
	low[u]=dfn[u]=++dfs_t;
	int child=0;
	sz[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		if(!dfn[v]){
			dfs(v,u);
			sz[u]+=sz[v];
			if(sz[v]%2&&low[v]>=dfn[u])
			fib[u]=true;
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=fa)
			iscut[u]=true;
			if(u==fa)child++;
		}
		low[u]=min(low[u],dfn[v]);
	}
	if(u==fa&&child>=2)
	iscut[u]=true;
}
int a[MAXN];
void solve(){
	int n=read_int(),m=read_int();
	LL ans=0;
	edge_cnt=0,dfs_t=0;
	_rep(i,1,n){
		a[i]=read_int();
		head[i]=0;
		dfn[i]=0;
		iscut[i]=0;
		fib[i]=0;
		ans+=a[i];
	}
	while(m--){
		int u=read_int(),v=read_int();
		Insert(u,v);
		Insert(v,u);
	}
	if(n%2==0){
		enter(ans);
		return;
	}
	dfs(1,1);
	int det=Inf;
	_rep(i,1,n){
		if(!iscut[i])
		det=min(det,a[i]);
		else if(!fib[i])
		det=min(det,a[i]);
	}
	enter(ans-det*2);
}
int main(){
	int T=read_int();
	while(T--){
		solve();
	}
	return 0;
}

CVBB ACM Team

目录

补题情况

题解

J. Defend Your Country

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

补题情况

题解

J. Defend Your Country

题意

题解

页面工具