第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） H Line Graph Matching

66 阅读 0 评论 44 点赞

我是靠谱客的博主寂寞煎蛋，最近开发中收集的这篇文章主要介绍第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳） H Line Graph Matching，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+10;
struct Edge{
	int to,nxt;
	bool cut;
	int val;
}edge[MAXN];
int head[MAXN],tot=0;
int low[MAXN],dfn[MAXN],sta[MAXN];
int Index,top;
bool instack[MAXN],cut[MAXN];
int addblock[MAXN],belong[MAXN];
int bridge,block;
void addedge(int u,int v,int w){
	edge[tot]={v,head[u],false,w};head[u]=tot++;
}
int viss[MAXN],num=0;
void tarjan(int u,int pre){
	int v;
	low[u]=dfn[u]=++Index;
	sta[top++]=u;
	instack[u]=true;
	int precnt=0;
	for(int i=head[u];~i;i=edge[i].nxt){
		v=edge[i].to;
		if(v==pre&&precnt==0){precnt++;continue;}
		if(!dfn[v]){
			tarjan(v,u);
            num++;
			if(low[u]>low[v]) low[u]=low[v];
			if(low[v]>dfn[u]){
				bridge++;
				edge[i].cut=true;
                edge[i^1].cut=true;
			}
		}else if(instack[v]&&low[u]>dfn[v]){
            low[u]=dfn[v];
        }
	}
	if(low[u]==dfn[u]){
        block++;
        do{
            v=sta[--top];
            instack[v]=false;
            belong[v]=block;
        }while(v!=u);
    }
}
void init(){
	tot=0;memset(head,-1,sizeof head);
}
vector<int> g[MAXN]; int cnt[MAXN];
void dfss(int x,int fa){
    for(auto i:g[x]){
        if(i==fa) continue;
        dfss(i,x);
        cnt[x]+=cnt[i]+1;
    }
}
struct node{
    int a,b,c;
}kep[MAXN];
int n,m;long long sum=0;
void solve(int n){
	memset(dfn,0,sizeof dfn);
	memset(instack,false,sizeof instack);
	memset(addblock,0,sizeof addblock);
	memset(cut,false,sizeof cut);
	Index=top=bridge=0;
	int fl=0;
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			if(i!=1) fl=1;
			tarjan(i,i);
		}
	}
    for(int i=1;i<=m;i++){
        int a=kep[i].a,b=kep[i].b;
        // cout<<a<<" "<<b<<endl;
        if(belong[a]==belong[b]){
            cnt[belong[a]]++;
        }else{
            g[belong[a]].push_back(belong[b]);
            g[belong[b]].push_back(belong[a]);
        }
    }    
    dfss(1,0);
    // for(int i=1;i<=block;i++) cout<<cnt[i]<<endl;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=head[i];~j;j=edge[j].nxt){
            int to=edge[j].to;
            if(edge[j].cut==false) ans=max(ans,sum-edge[j].val);
            else{
                if(min(cnt[belong[i]],cnt[belong[to]])%2==0){
                    ans=max(ans,sum-edge[j].val);
                }
            }
        }
    }
    cout<<ans<<endl;
}

int32_t main(){
	    scanf("%lld%lld",&n,&m);
		init();
        
		for(int i=1;i<=m;i++){
			int a,b,c;scanf("%lld%lld%lld",&a,&b,&c);
            kep[i]={a,b,c};
			addedge(a,b,c);
            addedge(b,a,c);
            sum+=c;
		}
        if(m%2==0){
            cout<<sum<<endl;
        }else{
            solve(n);
        }
}