记录编号	192080	评测结果	AAAAAAAAAAAAAAAA
题目名称	[CEOI1997]参观洞穴	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2015-10-09 19:03:11	内存使用	0.56 MiB

#include<cstdio>
#include<deque>
#include<iostream>
using namespace std;
const int SIZEN=510,maxn=0x7fffffff/2;
int N,K,ma=maxn;
int ans[SIZEN]={0},nowans[SIZEN]={0};
bool visit[SIZEN]={0};
deque<pair<int,int> > s[SIZEN];
void read()
{
	scanf("%d%d",&N,&K);
	int fr,to,C;
	for(int i=1;i<=3*N/2;i++)
	{
		scanf("%d%d%d",&fr,&to,&C);
		s[fr].push_back(make_pair(to,C));
		s[to].push_back(make_pair(fr,C));
	}
}
bool check(int fa,int x)
{
	for(int i=0;i<s[fa].size();i++)
	{
		int v=s[fa][i].first;
		if(visit[v]||v==x) continue;
		int cnt=0;
		for(int j=0;j<s[v].size();j++) 
		{
			int w=s[v][j].first;
			if(visit[w]&&w!=1&&w!=N) cnt++;
		}
		if(cnt>=2) return 1;
	}
	return 0;
}
bool connect(int x,int y)
{
	for(int i=0;i<s[x].size();i++)
		if(s[x][i].first==y) return 1;
	return 0;
}
void dfs(int x,int tot,int now,int fa,int last)//last为最后出现的一个外房间
{
	if(now>ma) return;
	nowans[tot]=x;
	if(tot==N) 
	{
		ma=now;
		for(int i=1;i<=N;i++) ans[i]=nowans[i];
		return;
	}
	if(check(fa,x)) return;
	visit[x]=1;
	int P=0;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i].first;
		P=last;
		if(visit[v]==0)
		{
			if(v<=K)
			{
				if(connect(last,v)) P=v;
				else continue;
			}
			if(s[x][i].second==1) dfs(v,tot+1,now+1,x,P);
			else dfs(v,tot+1,now,x,P);
		}
	}
	visit[x]=0;
}
void work()
{
	dfs(1,1,0,0,1);
	for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}
int main()
{
	freopen("cave.in","r",stdin);
	freopen("cave.out","w",stdout);
	read();
	work();
	return 0;
}