HZOJ 星际旅行

傷城~ 2021-11-09 09:12 360阅读 0赞

正解欧拉路，其实看完题解还是挺简单的，由于对欧拉路这种东西没怎么接触过，所以考试时没想出来，知识还是有漏洞啊。

另外这题的题解写的也不是很清楚（可能大佬作者觉得这是一道送分题……），首先判断联通（注意是边联通，即使是有一个点孤立也不会影响方案数），可以用dfs或并查集，注意dfs有一个坑点，不要直接就从1开始搜，因为1可能是那个被孤立的点。然后就可以求方案数了：

将无向图拆成双向边，显然每个点的度为偶数，是欧拉路，那么问题就转化成了从中去掉两条边使其仍然是欧拉路，题目中特别提醒了自环，所以分三种情况：

1.去掉两个自环，显然还是欧拉路，ans+=（num）\*（num-1）/2;然而我一开始忘了除二（之前犯过的错误，该打）。

2.去掉一个自环和一条普通边，自环显然没问题，但是去掉普通边之后仍然是欧拉路吗？可以从去掉的那条边的反边起点开始走过去，那么每个点的度数仍然为偶数，仍然为欧拉路，ans+=num\*（m-num）;

3.剩下去掉普通边的情况了，怎么去才合法呢？去掉一个点的一条入边和一条出边，那么显然仍然是欧拉路，证明同上。去掉其他边呢？并不满足题意。所以ans+=$C\_\{du\_i\}^\{2\}$。

#include<iostream>
    #include<cstdio>
    #define MAXN 100100
    #define int LL
    #define LL long long
    #define min(a,b) ((a)<(b)?(a):(b))
    using namespace std;
    struct edge
    {
    	int u,v,nxt;
    	#define u(x) ed[x].u
    	#define v(x) ed[x].v
    	#define n(x) ed[x].nxt
    }ed[MAXN*4];
    int first[MAXN],num_e;
    #define f(x) first[x]
    int n,m;
    LL C[500010][5];
    void get_C()
    {
    	C[0][0]=1;
    	for(int i=1;i<=500000;i++)
    	{	
    		C[i][0]=1;
    		for(int j=1;j<=min(i,4);j++)	
    			C[i][j]=C[i-1][j]+C[i-1][j-1];
    	}
    }
    bool v[MAXN],ve[MAXN*4];
    void pd(int x,int fa)
    {
    	v[x]=1;
    	for(int i=f(x);i;i=n(i))
    	{
    		ve[i]=1;
    		if(v(i)!=fa&&!v[v(i)])pd(v(i),x);
    	}
    }
    int num,ans;
    int du[MAXN];
    inline int read();
    inline void add(int u,int v);
    signed main()
    {
    	get_C();
    	n=read(),m=read();int a,b;
    	for(int i=1;i<=m;i++)
    	{
    		a=read(),b=read();
    		add(a,b);add(b,a);
    		if(a==b)num++;
    		else	du[a]++,du[b]++;
    	}
    	for(int i=1;i<=n;i++)if(du[i]){pd(i,0);break;}
    	for(int i=1;i<=num_e;i++)if(!ve[i]){puts("0");return 0;}
    	ans+=num*(num-1)/2;
    	ans+=num*(m-num);
    	for(int i=1;i<=n;i++)
    		ans+=C[du[i]][2];
    	cout<<ans<<endl;
    }
    inline void add(int u,int v)
    {
    	++num_e;
    	u(num_e)=u;
    	v(num_e)=v;
    	n(num_e)=f(u);
    	f(u)=num_e;
    }
    inline int read()
    {
    	int s=0;char a=getchar();
    	while(a<'0'||a>'9')a=getchar();
    	while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
    	return s;
    }

转载于:https://www.cnblogs.com/Al-Ca/p/11209321.html