noip 模拟赛 星系旅行题解

一个利用欧拉回路的试题...

根据题意要求，我们分析一下可以看出：一条边拆成两条边，那么原题等价于删去两条边后原图中仍然存在一条欧拉回路

同时图中存在自环

分析：

①：删去一个自环和任意一条其他边

②：删去两条非自环的边

我们分别来讨论这两种情况，首先讨论一下②

根据欧拉回路的性质以及题意，原图中所有点的度数一定是偶数，再考虑到没有重边，所以一条边连接的两点会分别获得2的度

那么如果我们删去的两条边没有交点，我们就会产生四个度为奇数的点，而这显然是不存在欧拉回路的

所以我们显然会要求所有删掉的两条边一定有一个交点

这样我们只需要枚举交点是哪个点即可

而如果我们删了一个自环，那么对这个点的度数是没有任何影响的（自环会对这个点的度产生一个2的贡献）

所以我们如果删了一个自环，剩下的边可以随意删不受影响

可是这就会产生一个问题：如果这次删了一个自环，第二次又删了一个自环，这样会产生重复！

所以我们只需要在最后去个重，也就是减掉重复的自环选择即可

贴代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
struct node
{
int lx,rx;
}p[100005];
int f[100005];
ll sel[100005];
ll inr[100005];
int has[100005];
int n,m;
int findf(int x)
{
if(x==f[x])
{
return x;
}
return f[x]=findf(f[x]);
}
int main()
{
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p[i].lx,&p[i].rx);
if(p[i].lx==p[i].rx)
{
sel[p[i].lx]++;
continue;
}
inr[p[i].lx]++;
inr[p[i].rx]++;
int f1=findf(p[i].lx);
int f2=findf(p[i].rx);
f[f1]=f2;
}
ll cnt=0,s=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i&&(inr[i]||sel[i]))
{
cnt++;
}
s+=sel[i];
}
if(cnt>1)
{
printf("0n");
return 0;
}
ll ret=0,ans=0;
for(int i=1;i<=n;i++)
{
ret+=sel[i]*(m-1);
if(inr[i]<2)
{
continue;
}
ans+=inr[i]*(inr[i]-1)/2;
}
ret-=s*(s-1)/2;
ans+=ret;
printf("%I64dn",ans);
return 0;
}

最后

以上就是飘逸路灯为你收集整理的noip 模拟赛 星系旅行题解的全部内容，希望文章能够帮你解决noip 模拟赛 星系旅行题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。