欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

清华数据结构旅行商问题TSPAC100

程序员文章站 2022-07-14 12:53:51
...

本题的提示要用拓扑

本人想着试着用拓扑,但是发现要求的数组太大,没法构建相应的边,故放弃了

因此想了另一个办法,代码如下

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;
#define maxn 1000001
int maxx;
struct listnode
{
	listnode*pre;
	int indu_num = 0;//记录indu指向的j,即i->j
	listnode() {}
	listnode(int n, listnode*p = NULL) :indu_num(n), pre(p) {}
};
struct p_list
{
	listnode*head, *trail;
	int flag = 1,length=1;
	void init();
	// ~p_list();
	p_list() { init(); }
	void insert(int&out);
	// p_list&operator=(p_list&a);
};
void p_list::init()
{
	head = new listnode();
	trail = new listnode();
	head->pre = trail;
	trail->pre = NULL;
}
void p_list::insert(int&out)//越先进入的元素,越靠近队尾
{
	listnode*p = new listnode(out);
	p->pre = head->pre;
	head->pre = p;
}
p_list edge[maxn];
int dsf(listnode*p, int i)//i是上一层的值
{
	auto q = p->pre;
	int count=1;
	while (q != edge[i].trail)
	{
		if(edge[i].flag==0){
			count+=edge[i].length;break;
		}
		count+=dsf(edge[q->indu_num].head, q->indu_num);
		if (edge[i].length >count);//最开始为1,后来为每个出边返回值+1,count=1就从来没变过
		else edge[i].length = count;
		q = q->pre;
		count=1;
	}
	edge[i].flag = 0;
	if (maxx>edge[i].length);
	else maxx = edge[i].length;
	return edge[i].length;
}
void travel(int n)
{
	int count = 1;
	maxx = count;
	for (auto i = 0; i<n; i++)
	{
		if (edge[i].flag == 0);
		else {
			auto p = edge[i].head;
			dsf(p, i);
		}
	}
}
int main()
{
#ifndef _OJ_
	freopen("travelin.txt", "r", stdin);
	// freopen("travelout.txt", "w", stdout);
#endif
	int i, j, m, n;//i,j是边的坐标,cap是边的总数
	scanf("%d %d", &n, &m);//m是有效边的数目,n是点的个数
	while (m--) {
		scanf("%d %d", &i, &j);
		edge[i - 1].insert(--j);
	}
	travel(n);
	printf("%d\n", maxx);
}

这里的思想是,通过flag,保证之前走过的边,不会再走一次

每次当某点所有的出边都被访问完毕之后,就令其flag=0。

这里是这样考虑的,因为改点所有的出边都被访问,如果再次访问,其结果都是一样的,即,该点对应的最大路径长度不变,因此直接用当前长度加上该点的最大路径长度即可!

附上自己认为是最快运行速度的截图,嘻嘻!清华数据结构旅行商问题TSPAC100