问题 A: 星际旅行
时间限制: 1 Sec 内存限制: 256 MB
题面
题面谢绝公开。
考试心路历程
拿到这道题感觉很懵逼，所以先搞的T2和T3，最后码了个暴力，结果还不如直接输出‘0’得分高。
暴力码了T10，花了30多分钟，感觉亏大了。主要调起来比较恶心。各种玄学低错层出不穷。
开始码出来后交了，又拉下来手模一组样例测了，hack了，整个人开始慌张，然后就调。调了半天终于过了手模样例和题示样例，觉得稳了，就交了。
后来看提交记录，之前交的也是T10……亏了亏了……
总结一下，别人这道题都是轻易拿50、80，我只拿了10，除了暴力太暴力以外，还是时间分配不合理。同样也是没仔细想完全没往欧拉回路那里想。
还是考试经验不足和实力不足的双重叠加。问题转化能力也要差很多。
题解
每个边拆成两条边，问题等价为删掉两条边，图中仍满足存在一个欧拉路。
给出欧拉路定义：欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次。
得到欧拉路判定方式：所有点度都是偶数，或者恰好有两个点度是奇数，则有欧拉路。若有奇数点度，则奇数点度点一定是欧拉路的起点和终点，否则可取任意一点作为起点。（无向图）
根据欧拉图的判定方式我们分三种情况进行讨论：1.去掉任意2个自环 2.去掉任意1个自环和任意一条边 3.去掉两条有公共顶点的边
所以设自环数为sum_cir，情况1为：sum_cir*(sum_cir-1)，
设每个点不包括自环的度为du[i]，则情况2为：sum_cir*($sum(du[i])$)/2（每个边连两个点，所以∑du[i]把每个边算了两次）。
情况3为：$sum (du[i]*(du[i]-1)/2$，
(可以按组合数学的思路：从与i点相连的du[i]条边里面选出两个删掉，即为：$C_{du[i]}^2$，化简就是这个了。)
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<cmath> #include<vector> #define rint register int #define ll long long using namespace std; ll n,m,fr,to; ll tot,first[100005],du[100005]; ll sum,sum2,rd[100005]; ll fa[100005]; ll ans=0; inline ll get_fa(ll x) { if(fa[x]==x)return x; return fa[x]=get_fa(fa[x]); } int main() { scanf("%lld %lld",&n,&m); for(ll i=1;i<=n;++i)fa[i]=i; for(ll i=1;i<=m;++i) { scanf("%lld %lld",&fr,&to); if(fr==to)sum++; else { du[fr]++,du[to]++; ll f1=get_fa(fr),f2=get_fa(to); fa[f1]=f2; } rd[fr]++,rd[to]++; } ll lin; for(ll i=1;i<=n;++i) if(rd[i]){lin=i,get_fa(i);break;} for(ll i=1;i<=n;++i) { if(rd[i]&&get_fa(i)!=fa[lin]) { cout<<0<<endl; return 0; } } for(ll i=1;i<=n;++i) ans+=(du[i]-1)*du[i]/2,sum2+=du[i]; ans+=sum*sum2/2; ans+=sum*(sum-1)/2; printf("%lld ",ans); return 0; }