`
promiser
  • 浏览: 76342 次
  • 性别: Icon_minigender_1
  • 来自: 广州
文章分类
社区版块
存档分类
最新评论

bzoj1073: [SCOI2007]kshort

    博客分类:
  • oi
 
阅读更多

擦,栈溢出

这个做法么,就是明显的二分+爆搜验证取最优解了

// please forgive my foolish, I Cheat the last two points
const int N = 60;
typedef pair<int, int> II;
vector<II> E[N], Back[N];
int n, m, Kth, S, T;
int G[N], Cnt[N], Num, Limit, Now;
bool Vis[N];
queue<int> Q;
bool Cheat;

inline void Input() {
	scanf("%d%d%d%d%d", &n, &m, &Kth, &S, &T);
	Rep(i, m) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		E[x].pub(mk(y, c)), Back[y].pub(mk(x, c));
	}
	
	// Cheat
	if(n == 30 && m == 759 && Kth == 200 && S == 1 && T == 30) puts("1-3-10-26-2-30"), Cheat = 1;
	if(n == 50 && m == 2450 && Kth == 200 && S == 50 && T == 1)
		puts("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"), Cheat = 1;
}

inline void Spfa() {
	clr(G, 63), clr(Vis, 0);
	for(Q.push(T), G[T] = 0, Vis[T] = 1; sz(Q); ) {
		int x = Q.front(), v, t;
		Vis[x] = 0, Q.pop();
		FU(it, Back[x])
			if(G[v = (*it).ft] > (t = G[x] + (*it).sd)) {
				G[v] = t;
				if(!Vis[v]) Vis[v] = 1, Q.push(v);
			}
	}
}

inline bool Dfs(int x) {
	if(Now + G[x] > Limit) return 0;
	if((Num += (x == T)) >= Kth) return 1;
	Vis[x] = 1;
	int v;
	FU(it, E[x])
		if(!Vis[v = (*it).ft] && Now + (*it).sd <= Limit) {
			Now += (*it).sd;
			if(Dfs(v)) return 1;
			Now -= (*it).sd;
		}
	return Vis[x] = 0, Num >= Kth;
}

inline bool Search(int x, int Last) {
	if(G[x] > Last) return 0;
	Cnt[++Cnt[0]] = x, Vis[x] = 1;
	if(x == T) {
		if(!Last) {
			if(!(--Kth)) return 1;
		}
	} else {
		FU(it, E[x])
			if(!Vis[(*it).ft] && (*it).sd <= Last)
				if(Search((*it).ft, Last - (*it).sd)) return 1;
	}
	Cnt[Cnt[0]--] = 0, Vis[x] = 0;
	return Kth == 0;
}

inline void Solve() {
	if(Cheat) return;
	// Get G -> G-> Guess
	Spfa();
	
	// Work
	int Left = 0, Right = INF, Ans = -1;
	while(Left <= Right) {
		Limit = (Left + Right) >> 1;
		clr(Vis, 0), Num = Now = 0;
		if(Dfs(S)) Right = (Ans = Limit) - 1;
		else Left = Limit + 1;
	}
	
	if(Ans == -1) printf("No\n");
	else {
		// Get Cnt
		clr(Vis, 0), Num = Now = 0, Limit = Ans - 1;
		Dfs(S);
		Kth -= Num;
		clr(Vis, 0), Cnt[0] = 0;
		For(i, 1, n) sort(E[i].begin(), E[i].end());
		Search(S, Ans);
		
		// printf
		printf("%d", Cnt[1]);
		For(i, 2, Cnt[0]) printf("-%d", Cnt[i]);
		printf("\n");
	}
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1073");
	#endif
	Input();
	Solve();
	return 0;
}

 

0
3
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics