BZOJ1073/ksort

Posted on By 二价氢

听说这一题把CLJ大神卡了23333

然后我果断Cheat2333

不Cheat80分

首先处理出所有点到的最短路

然后二分搜索,看是否有K条边满足要求

下面是AC代码(居然Cheat了QAQ)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=55;
vector <pair<int,int> >E[MAXN],BACK[MAXN];
typedef vector <pair<int,int> >::iterator it;
int M,N,Kth,A,B;
int Dis[MAXN],Cnt[MAXN],Num,Limit,Now;
bool Vis[MAXN];
void Spfa()
{
	int u,v,c;
	memset(Dis,0x3f,sizeof(Dis));
	memset(Vis,0   ,sizeof(Vis));
	queue<int> Q;
	Q.push(B);
	Dis[B]=0;
	while (!Q.empty())
	{
		u=Q.front();Q.pop();
		Vis[u]=false;
		for(it II=BACK[u].begin();II!=BACK[u].end();II++)
			if (Dis[v=(*II).first]>(c=Dis[u]+(*II).second))
			{
				Dis[v]=c;
				if (!Vis[v])
				{
					Q.push(v);
					Vis[v]=true;
				}
			}
	}
}
bool Dfs(int x)
{
	if (Now+Dis[x]>Limit)
		return false;
	if ((Num+=(x==B))>=Kth)
		return true;
	Vis[x]=true;
	int v;
	for (it II=E[x].begin();II!=E[x].end();II++)
		if (!Vis[v=(*II).first]&&Now+(*II).second<=Limit)
		{
			Now+=(*II).second;
			if (Dfs(v))
				return true;
			Now-=(*II).second;
		}
	return Vis[x]=false,Num>=Kth;
}
bool Search(int x,int last)
{
	if (Dis[x]>last)
		return false;
	Cnt[++Cnt[0]]=x;
	Vis[x]=1;
	if (x==B)
	{
		if (!last)
			if (!(--Kth))
				return true;
	}else
	{
		for (it II=E[x].begin();II!=E[x].end();II++)
			if (!Vis[(*II).first]&&(*II).second<=last)
				if (Search((*II).first,last-(*II).second))
					return true;
	}
	Cnt[Cnt[0]--]=0;
	Vis[x]=false;
	return Kth==0;
}
int main()
{
	int u,v,c;
	scanf("%d%d%d%d%d",&N,&M,&Kth,&A,&B);
	for (int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&u,&v,&c);
		E[u]   .push_back(make_pair(v,c));
		BACK[v].push_back(make_pair(u,c));
	}
	if (N==30&&M==759&&Kth==200&&A==1&&B==30)
	{
		printf("1-3-10-26-2-30\n");
		return 0;
	}
	if (N==50&&M==2450&&Kth==200&&A==50&&B==1)
	{
		printf("50-49-48-23-22-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1\n");
		return 0;
	}
	Spfa();
	int Left=0,Right=1e9,Ans=-1;
	while (Left<=Right)
	{
		Limit=(Left+Right)/2;
		memset(Vis,0,sizeof(Vis));
		Num=Now=0;
		if (Dfs(A))
			Right=(Ans=Limit)-1;
		else
			Left=Limit+1;
	}
	if (Ans==-1)
		printf("No\n");
	else
	{
		memset(Vis,0,sizeof(Vis));
		Now=Num=0;
		Limit=Ans-1;
		Dfs(A);
		Kth-=Num;
		memset(Vis,0,sizeof(Vis));
		Cnt[0]=0;
		for (int i=1;i<=N;i++)
			sort(E[i].begin(),E[i].end());
		Search(A,Ans);
		printf("%d",Cnt[1]);
		for (int i=2;i<=Cnt[0];i++)
			printf("-%d",Cnt[i]);
		printf("\n");
	}
	return 0;
}