2021ICPC沈阳 H.Line Graph Matching(dfs树求割边+简单树形dp)2021ICPC沈阳 H.Line Graph Matching(dfs树求割边+树形dp)

51 阅读 0 评论 34 点赞

我是靠谱客的博主凶狠火车，最近开发中收集的这篇文章主要介绍2021ICPC沈阳 H.Line Graph Matching(dfs树求割边+简单树形dp)2021ICPC沈阳 H.Line Graph Matching(dfs树求割边+树形dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2021ICPC沈阳 H.Line Graph Matching(dfs树求割边+树形dp)

前言：思路感觉并不难想，主要是题目太难读懂。

题意：简化了就是在原图中选择相邻的两条边进行配对，配对后产生的贡献为两边权值之和，不能重复选边配对。

前置芝士：dfs树

题解：

1.首先可以比较容易的知道，如果有偶数条边肯定可以把所有的边都选上（可以用dfs树来简单证明，如果dfs树的一个节点回边的数量加上连向儿子的边的数量为偶数，那么就可以完美配对；如果为奇数，那么用上这个节点连上父亲的边，就可以完美匹配，若用了连向父亲的边，那么父亲节点在计算连向儿子的边的时候就要减一，这样递归上去，可以知道偶数条边一定可以全选）。

2.接下来讨论奇数边的情况，首先比较简单的来想这个问题，奇数条边的图，我们去掉一条边不就变成偶数条边的图了吗，就可以归到上面的情况了，所以只需要删掉一条权值最小的边不就行了吗。但是我们会发现，如果删掉的这条边是割边，那么会分成两个连通块，如果如果连通块的边的数量为奇数，那么肯定导致这个连通块有一条边不能完美匹配，所以我们删掉的边只能是两种边[1]非割边(删掉了之后形成了一个偶数条边的连通图)[2]割边中删掉了这条割边之后连通块边数为偶数的边，以上两种情况的边权取最小值为minn，输出答案sum-minn即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int to;
int id;
ll w;
};
ll vis[200009];
vector<edge> g[200009];
int dp[200009];//用来求割边，详情请见博客上方连接
int bian[200009];//bian[i]表示子树中，以i为节点的子树有多少条边(子树节点连到i的祖先的边不算在内)
int dep[200009];
int n,m;
void dfs(int now,int fa){
dep[now] = dep[fa] + 1;
int id;
for(auto j : g[now]){
if(j.to == fa){
id = j.id;
continue;
}
if(dep[j.to]){
if(dep[j.to] > dep[now]){
dp[now]--;
}else{
dp[now]++;
bian[j.to]++;//回边
}
}else{
dfs(j.to,now);
dp[now] += dp[j.to];
bian[now] += (bian[j.to] + 1);//这个1指的是now连向儿子的边
}
}
if(now != 1&&dp[now] == 0 && (bian[now]) % 2 == 1){//dp[now] == 0表示这个节点连向父亲的边为割边
//bian[now] % 2 == 1表示删掉连向父亲的边之后，其子树形成的连通图边的数量为奇数
vis[id] = 2000000000;//设为无穷大表示不参与选最小的边的统计
}
}
int main(){
scanf("%d %d",&n,&m);
ll sum = 0;
for(int i = 1;i <= m;i++){
int u,v;
ll w;
scanf("%d %d %lld",&u,&v,&w);
sum += w;
vis[i] = w;
edge p;
p.id = i;p.w = w;p.to = v;
g[u].push_back(p);
p.to = u;
g[v].push_back(p);
}
if(m % 2 == 0){//偶数直接输出
printf("%lld",sum);
return 0;
}
dfs(1,0);
ll minn = 2000000000;
for(int i = 1;i <= m;i++){
minn = min(vis[i],minn);
}
printf("%lld",sum-minn);
return 0;
}