NOIP2019 旅行

注意！注意！前方高能！本题卡常！！！

我们发现，所有的狗血剧情都在告诉我们，树的话直接dfs就出来了

那么基环树呢？

其实只要暴力删边，理论上的复杂度是可以过的qwq

但是删哪条边呢？

这里要引出一个基环树的常用操作：拓扑排序求环。具体方法是：在基环树上拓扑排序，然后拓扑序列中不存在的节点就是环中的节点了。

最后要用到环中的边的时候有一个小技巧，就是存边的时候（我用的是邻接表存双向边）按



input(x,y,z);

if(x>y) swap(x,y);

add(x,y,z);add(y,x,z);

的顺序存。

这样找边去重的时候就比较好找。。。（我也表述不太明白，具体看代码吧~）

Code



#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N = 1e5+1;

int n,m,r[N];

int h[N],cnt,delu,delv;//假装 del_u-v 这条边已经被删去了qwq

struct edge

{

	int nxt;

	int to;

}e[N];

int ans[N],ans1[N];

int qh=0,qt=1,qtp[N],tp[N],vis[N],visu[N],visv[N],tpcnt;//巨丑的代码qwq

inline void readx(int &x)

{

	x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-48;ch=getchar();}

}

inline void add(register int u,register int v)

{

	e[++cnt].nxt=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

inline void topo()

{

    for(register int i=1;i<=n;++i) vis[i]=1;

    for(register int u=1;u<=n;++u)

    {

        for(register int i=h[u];i;i=e[i].nxt)

        {

            register int v=e[i].to;

            ++tp[u];++tp[v];

        }

    }

    for(register int i=1;i<=n;++i) if(tp[i]==2) qtp[qt++]=i;

//    for(int i=1;i<=n;++i) printf("%d ",qtp[i]);printf("\n");

    while(qt>qh)

    {

        register int u=qtp[++qh];vis[u]=0;

        for(register int i=h[u];i;i=e[i].nxt)

        {

            register int v=e[i].to;

            tp[u]-=2;tp[v]-=2;

            if(tp[v]==2&&vis[v]) qtp[qt++]=v;

        }

    }

    for(register int u=1;u<=n;++u)

        if(vis[u]==1)

        {

            for(register int i=h[u];i;i=e[i].nxt)

            {

                register int v=e[i].to;

                if(vis[v]==1&&u<v)

				{

					visu[++tpcnt]=u;visv[tpcnt]=v;

				}

            }

        }

}

inline void update()

{

	for(register int i=1;i<=n;++i)

	{

		if(ans1[i]==ans[i]) continue;

		if(ans[i]==0) {for(register int j=1;j<=n;++j) ans[j]=ans1[j];return;}

		if(ans1[i]>ans[i]) return;

		//ans1[i]<ans[i]

		for(register int j=i;j<=n;++j) ans[j]=ans1[j];return;

	}

}

inline void dfs(register int u,register int fa)

{

	ans1[++cnt]=u;

    priority_queue <int,vector<int>,greater<int> > q;//小根堆

	for(register int i=h[u];i;i=e[i].nxt)

	{

		register int v=e[i].to;

		if(v==fa||(u==delu&&v==delv)||(u==delv&&v==delu)) continue;

		q.push(v);

	}

	while(!q.empty())

	{

		register int v=q.top();q.pop();

		dfs(v,u);

	}

}

signed main()

{

	readx(n);readx(m);

	for(register int i=1;i<=m;++i)

	{

		int u,v;readx(u);readx(v);

		if(u>v) swap(u,v);

		add(u,v);add(v,u);

	}

	cnt=0;

	if(m==n-1)

	{

		dfs(1,0);

		for(register int i=1;i<=n;++i) ans[i]=ans1[i];

	}

	else

	{

		topo();

		for(register int i=1;i<=tpcnt;++i)

		{

			cnt=0;

			delu=visu[i];delv=visv[i];

			dfs(1,0);

			update();

		}

	}

	for(register int i=1;i<=n;++i)

		printf("%d ",ans[i]);

	return 0;

}

其实代码也就是看106行到107行那里，别的地方写得太丑了没法看，而且自己基本能写出来，加油哦qwq！

巴特西

NOIP2019 旅行

注意！注意！前方高能！本题卡常！！！

那么基环树呢？

最新文章

热门文章