• 欧拉路径！

    呃在昨晚的破防之下我并不想学这东西所以留到今晚？属于是懒爆了。那么我们来看，定义的话其实前面写过了在这里插入图片描述
    其实主要是分两个方面:
    1.图是否联通，是什么图
    2.这个图每个点的度数或者（出度入度）什么的若是符合就行。
    偷偷总结一下：（在符合条件1的情况下）
    如果是回路，那么有每个点的度数 出=入 或者 度数为偶数，那么如果不是回路那么在有向图中相当于多插入一个节点进去，那么其出度肯定比入度多1，那要是无向的话相当于你删除一条边，所以就有两个点的度数为奇数。
    行P7771 【模板】欧拉路径

    #include
using namespace std;
int n,m,len=0,last[2000001];
int in[2000001],out[2000001],q[2000001],tot=0;
struct pp
{
	int x,y,next;
};pp p[2000001],L[2000001];
bool v[2000001];
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y>y.y;
}
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
} 
void dfs(int x)
{
	for(int i=last[x];i!=-1;i=last[x])
	{
		last[x]=p[i].next;
		int y=p[i].y;dfs(y);
	}
	q[++tot]=x;
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(v,false,sizeof(v));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		L[i].x=x,L[i].y=y;in[y]++,out[x]++;
	}
	bool pd=false;int sumin=0,sumout=0,ST=1;
	for(int i=1;i<=n;i++)
	{
		if(in[i]!=out[i]) pd=true;
		if(out[i]-in[i]==1) sumout++,ST=i;
		if(in[i]-out[i]==1) sumin++;
	}
	if(pd&&!(sumin==1&&sumout==1)) //如果不是欧拉回路，也不是欧拉路径 
	{
		printf("No");
		return 0;
	}
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++) ins(L[i].x,L[i].y);
	dfs(ST);
	for(int i=1;i<=tot;i++) printf("%d ",q[i]);
//	while(tot) printf("%d ",q[tot--]);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    欸有好学的同学就要问啦，问什么要先走完所有循环再压入栈呢，就不能直接压入嘛，那么手推一组 1 -> 2 , 1 -> 3 , 3 ->1，那么你要是直接压入的话就会导致二的错误，那么解决方案就是用栈反着存，因为中间可能会绕很多环，而第一次遍历时无法保证那个环遍历了没，但你反着存的话就可以保证将环全部先走完。若先走的不是环也没有问题，因为你可以在后面遍历那些环然后将他们塞进去，但是通过手模你发现如果先进去的不是环的话那么其实会被直接压入栈中，若是环的话会一直走下去。
    给出例题( > , < ),P1341 无序字母对好这一题是无向图我学会了些，最终处理的有点麻烦而已，只不过判断联通与否有些麻烦而已了，那么小细节无向图找点你学会了嘛？

    for(int i=0;i<=n;i++)
	{
		if(du[i]%2) 
		{
			cnt++;
			if(ST==-1) ST=i;
		}
	}
	if(cnt&&cnt!=2) 
	{
		printf("No Solution");
		return 0;
	}
	if(ST==-1)
	{
		for(int i=0;i<=n;i++) 
		{
			if(du[i]) 
			{
				ST=i;
				break;
			}
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    代码：（好想她不过肯定不会被看到）

    #include
using namespace std;
int n,m,len=0,last[100001],fa[100001],p[151][151];
int ans[10001],tot=0,du[10001],N=257;
int findfa(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=findfa(fa[x]);
}
void dfs(int x)
{
	for(int i=0;i<=n;i++)
	{
		if(p[x][i]) p[x][i]=p[i][x]=0,dfs(i);
	}
	ans[++tot]=x;
	return ;
}
int main() 
{
	memset(p,0,sizeof(p));memset(du,0,sizeof(du));
	scanf("%d",&m);n=257-1;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		char op[11];scanf("%s",op+1);
		p[op[1]][op[2]]=p[op[2]][op[1]]=1;	
		int fx=findfa(op[1]),fy=findfa(op[2]);fa[fx]=fy;
		du[op[1]]++,du[op[2]]++;
	}
	int cnt=0;
	for(int i=0;i<=n;i++)
	{
		if(fa[i]==i&&du[i]) cnt++;
	}
	if(cnt!=1) 
	{
		printf("No Solution");
		return 0;
	}
	int ST=-1;cnt=0;
	for(int i=0;i<=n;i++)
	{
		if(du[i]%2) 
		{
			cnt++;
			if(ST==-1) ST=i;
		}
	}
	if(cnt&&cnt!=2) 
	{
		printf("No Solution");
		return 0;
	}
	if(ST==-1)
	{
		for(int i=0;i<=n;i++) 
		{
			if(du[i]) 
			{
				ST=i;
				break;
			}
		}
	}
	dfs(ST);//printf("%c",ST);
	while(tot) printf("%c",ans[tot--]);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    P3520 [POI2011] SMI-Garbage这一题的思路是看出来它是欧拉回路，那么直接判断以及找环就行。小贴士：找环的时候，找了一个点就要判出哦。

    #include
using namespace std;
int n,m,len=-1,last[2000001],dfsx[2000001],low[2000001],dfs_x=0;
int q[2000001],tot=0,c[2000001],cnt=0,du[2000001];
bool v[2000001];
struct pp
{
	int x,y,next;
};pp p[2000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void dfs(int x,int st)
{
	q[++tot]=x;du[x]-=2;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(v[i]) continue ;v[i]=v[i^1]=true;
		if(y==st) 
		{
			q[++tot]=y;
			return ;
		}
		dfs(y,st);
		return ;
	}
}
int main()
{
	memset(last,-1,sizeof(last));memset(v,false,sizeof(v));   
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,c1,c2;scanf("%d%d%d%d",&x,&y,&c1,&c2);
		if(c1==c2) continue ;
		ins(x,y);ins(y,x);
		du[x]++,du[y]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]%2) 
		{
			printf("NIE\n");
			return 0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		while(du[i]) dfs(i,i),c[++cnt]=tot;
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",c[i]-c[i-1]-1);
		for(int j=c[i-1]+1;j<=c[i];j++) printf("%d ",q[j]);
		printf("\n");
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    P7684 [CEOI2005] Depot Rearrangement开始做点难题了，这个题目花了不少时间来看，这里介绍一种天才般的做法，不妨推一下，发现区间中只出现过一次的值是不用动的，没出现的要转，出现了一次以上的要转，那么可以尝试将其转化成二分图，那么咋建呢，左边作为每一个区间的点集，有n个，右边作为m个集装箱的种类，那么不妨设计一下状态，然后发现n*m+1被进入的次数最少时是最优的那么看博客吧（https://www.luogu.com.cn/problem/solution/P7684）。说说自己的理解：这一题若是想到二分图便很好处理了，不妨假想成为一个二分图求最大匹配的算法，那么发现其实这个题目是一定会成环的（因为题目要求每个都能匹配上），所以可以直接跑欧拉路径（主要是它要输出方案，所以要欧拉路径）。放一下别人的题解：（https://blog.csdn.net/u014609452/article/details/53493294）
    在这里插入图片描述
    ！！！
    大概懂了？实现好难啊QWQ，主要是边的操作了啦。

    #include
#define int long long 
using namespace std;
int n,m,len=-1,last[1000001],t[500][500],q[1000001],tot=0;
bool v[1000001];
vector<int > pos[500][500];
struct node 
{
	int x,y;
};node ans[1000001];
struct pp
{
	int x,y,next;
};pp p[1000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
} 
void dfs(int x)
{
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(v[i]) continue ;
		v[i]=true;dfs(y);q[++tot]=i;
	}
	return ;
} 
signed main()
{
	memset(last,-1,sizeof(last));memset(v,false,sizeof(v));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x;scanf("%lld",&x);
			t[i][x]++;pos[i][x].push_back((i-1)*m+j);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=2;k<=t[i][j];k++) ins(i,j+n);
			if(t[i][j]==0) ins(j+n,i);
		}
	}len=0;
	for(int i=n+1;i<=n+m;i++)
	{
		tot=0;dfs(i);
		int to=n*m+1;
		for(int i=1;i<=tot;i++)
		{
			int x=p[q[i]].x,y=p[q[i]].y;
			if(x>n) continue ;
			ans[++len].x=pos[x][y-n][--t[x][y-n]];
			ans[len].y=to;to=ans[len].x;
		}
		if(tot) ans[++len].x=n*m+1,ans[len].y=to;
	}
	printf("%lld\n",len);
	for(int i=1;i<=len;i++) printf("%lld %lld\n",ans[i].x,ans[i].y);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
  • 相关阅读:
    深度解读ChatGPT基本原理
    JVM 别和我说你还不知道这几种垃圾回收器？Serial ｜Parallel｜ParNew｜CMS｜G1｜ZGC
    极兔、百世快递的物流信息怎么批量查询？
    使用NNO区域进行色偏检测
    mybatis批量更新问题
    Day04 HTML标记
    携创教育：学位证和毕业证有什么区别？自考怎么申请学位证？
    Leetcode T49: 字母异位词分组
    ElasticSearch ( 一 ) 安装启动
    GAN 生成对抗神经网络
  • 原文地址：https://blog.csdn.net/cn_tigerhan/article/details/127873020