[7.18NOIP模拟测试5]星际旅行 题解

[7.18NOIP模拟测试5]星际旅行 题解
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说[7.18NOIP模拟测试5]星际旅行 题解,希望能够帮助大家进步!!!

题面(加密)

考场上靠打表yy出的规律进而想到的正解233333

可以把一条双向边拆成两条单向边,这样的话每个点度数都为偶数,符合欧拉图的定义。

那么题目可以转化为:去掉两条边,使图中存在一条欧拉路。

如果拆边还要满足欧拉路性质,就必须拆两条有公共顶点的边。

但是本题中明确给出含有自环,所以还有另外两种操作可以满足题意:

去掉两个自环,去掉一个自环一条边。

统计点的度数和自环数分类计算即可。

但是题中没有给图一定联通的条件,所以还要特判。

一定注意不能判点联通,点散一地没边连着对结果毫无影响.利用dfs或冰茶几判边联通即可。

//把命运交给打表找规律#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int N=1e5+5;int read()
{ int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;
}int n,m;int dg[N],po,fa[N],deg[N];int findf(int x)
{ if(fa[x]==x)return x; return fa[x]=findf(fa[x]);
}void merge(int x,int y)
{ int fx=findf(x),fy=findf(y); fa[fx]=fy;
}long long ans,sumdeg;int main()
{ n=read();m=read(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x=read(),y=read(); if(x!=y) dg[x]++,dg[y]++,merge(x,y); else po++; deg[x]++,deg[y]++; } int node=0; for(int i=1;i<=n;i++) if(deg[i]) { findf(i); node=i; break; } for(int i=1;i<=n;i++) { if(deg[i]&&findf(i)!=fa[node]) { puts("0"); return 0; } } for(int i=1;i<=n;i++) ans=ans+1LL*(dg[i]-1)*dg[i]/2,sumdeg+=1LL*dg[i]; long long ans1=1LL*po*sumdeg/2,ans2=1LL*po*(po-1)/2; cout<<ans+ans1+ans2<<endl; return 0;
} 

 

转载于:https://www.cnblogs.com/Rorschach-XR/p/11208549.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29647

发表评论