2021icpc沈阳 H Line Graph Matching(tarjan 求桥)

题意：

给定一个无向图，将原图中的点换成边，边换成点，如果原图中边1和边2公用一个端点A，那么生成图中边A的权值等于原图中边1+边2

让我们求生成图中最大加权匹配（选出一组边的集合，使得集合里没有两条边公用一个顶点，使得集合中边的边权和最大），求出最大边权和

首先这个题意有点曲折

按他的题意，如果两条边公用一个点，那么生成图中这两条边对应的点就一定有一条边，边权为这两条边的和

我们先来看两张图

这里因为a和b有公共顶点2，b和c有公共顶点3，所以生成图中a-b，b-c

这张图每两条边之间都有共同顶点（1），所以生成图中每个点与其他点均连有边

第一张图中如果我们选了a+b，则不能再选b+c

第二张图中我们可以选a+b，再通过选d+c，把所有点选上

我们可以看出，其实题意就是再原图中，如果两条边有共同顶点就可以选，同一条边只能选一次，求最大权值和

而他边的范围是n*(n-1)/2

可以证明如果是偶数条边，在都联通的情况下是可以都选完的

如果是奇数条边，我们就要在答案中减去一个影响最小的边

对于普通边可以直接取min

而对于桥

如果是  奇数-桥c-奇数，我们如果想删桥c，就要在左边删一个a，在右边删一个b，然后删掉桥c

总损失是a+b+c，这样显然是不划算的，我们可以使桥c-奇数变成一个偶数图，他们可以一个都不删掉，只删a即可，所以如果是奇数-桥-奇数，这个桥就不能参与取min了

如果是 偶数-桥-偶数，两边都可以取完，那这个桥就可以当作一个普通边来取min

结论就出来了，直接tarjan求桥在看是那种类型的桥，取一个min即可

代码如下

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define pll pair<int,int>
using namespace std;
const int N=4e5+10;
vector<pll> edg[N];
int siz[N];
int dfn[N],low[N],timestamp;
int minn,totedg;
int n,m;
int nodeedg[N];
int ans;
void tarjan(int u,int fa){
    dfn[u]=low[u]=++timestamp;
    siz[u]=nodeedg[u];
    for(auto t:edg[u]){
        int v=t.first;
        int w=t.second;
        if (!dfn[v]) {
            tarjan(v,u); 
            siz[u]+=siz[v];
            low[u]=min(low[u],low[v]);
            if (low[v]>dfn[u]) {
                if ((((siz[v]-1)/2)&1)==0){
                    minn=min(minn,w);
                }
            }
            else{
                minn=min(minn,w);
            }
        }
        else if(v!=fa) {minn=min(minn,w);low[u]=min(low[u],dfn[v]);}
        if (dfn[u]<dfn[v]) {totedg++;}
    }
}
signed main() {
    cin>>n>>m;
    fer(i,1,m){
        int uu,vv,w;
        cin>>uu>>vv>>w;
        edg[uu].pb({vv,w});
        edg[vv].pb({uu,w});
        ans+=w;
        nodeedg[uu]++;
        nodeedg[vv]++;
    }
    fer(i,1,n){
        if (!dfn[i]) {
            minn=2e9+10;
            totedg=0;
            tarjan(i,0);
            if(totedg&1) ans-=minn;
        }
    }
    cout<<ans;

}