Sgu/145

NPH问题 二分答案+搜索剪枝

//by hza
#include<cstdio>
 
const int MAX=100+10;
const int MAXP=500+10;
int n,m,S,T,K;
int cost[MAX][MAX];
int hash[MAX];
 
int max,less,l,r,find;
int answer;
int ans[MAX],top;
 
void dfs(int u,int sum)
{
	if(u==T)
	{
		++less;
		if(less>=K)find=true;
		return;
	}
	int v;
	for(v=1;v<=n;++v)
		if(cost[u][v]&&!hash[v])
		{
			if(cost[u][v]+sum<=max)
			{
				hash[v]=1;
				dfs(v,cost[u][v]+sum);
				hash[v]=0;
				if(find)
					return;
			}
		}
}
 
int check()
{
	int i;
	for(i=1;i<=n;++i)
		hash[i]=0;
	hash[S]=1;
	find=false;less=0;
	dfs(S,0);
	return find;
}
 
void search(int u,int sum)
{
	if(u==T)
	{
		if(sum==answer)find=true;
		return;
	}
	int v;
	for(v=1;v<=n;++v)
		if(cost[u][v]&&!hash[v])
		{
			if(cost[u][v]+sum<=answer)
			{
				hash[v]=1;
				search(v,cost[u][v]+sum);
				hash[v]=0;
				if(find)
				{
					ans[++top]=v;
					return;
				}
			}
		}
}
 
void get()
{
	int i;
	for(i=1;i<=n;++i)
		hash[i]=0;
	hash[S]=1;
	find=0;
	search(S,0);
	printf("%d %d\n%d ",answer,top+1,S);
	for(i=top;i>=1;--i)printf("%d ",ans[i]);
	printf("\n");
 
}
 
int main()
{
	freopen("145.in","r",stdin);
	freopen("145.out","w",stdout);
	int i,x,y,w;
	scanf("%d %d %d",&n,&m,&K);
	for(i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&w);
		cost[x][y]=cost[y][x]=w;
		r+=w;
	}
	scanf("%d %d",&S,&T);
	while(l+1<r)
	{
		max=(l+r)>>1;
		if(check())r=max;
		else l=max;
	}
	max=l+1;
	if(check())r=l+1;
	answer=r;
	get();
}