Noip2007 树网的核【Floyd+枚举】 Noip2012 选择客栈【乱搞】

tonyfang posted @ 2015年10月13日 14:38 in NOIP with tags c++ oi , 379 阅读

树网的核:只需要floyd然后枚举即可。

理论复杂度$O(n^4)$,因为常数小,所以可以过。

 

# include <stdio.h>
# include <algorithm>
# define LBW main
using namespace std;
int n,S,d[510][510];
int s[510],sn,head,tail,minn,maxx=-1,ans=1000000000;
inline int cmp(int a,int b) {
	return d[head][a]<d[head][b];
}
int LBW() {
	scanf("%d%d",&n,&S);
	for (int i=1;i<=n;++i) 
		for (int j=1;j<=n;++j)
			if(i!=j) d[i][j]=1000000000;
	for (int i=1,a,b,c;i<n;++i) {
		scanf("%d%d%d",&a,&b,&c);
		d[a][b]=d[b][a]=c;
	}
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if(d[i][k]+d[k][j]<d[i][j])
					d[i][j]=d[i][k]+d[k][j];
	// debug
	//for (int i=1;i<=n;++i) {
	//	for (int j=1;j<=n;++j)
	//		printf("%d ",d[i][j]);
	//	printf("\n");
	//}
	// debug end
	int maxlen=0;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			if(d[i][j]>maxlen && d[i][j]!=1000000000) {
				maxlen=d[i][j];
				head=i;
				tail=j;
			}
	for (int i=1;i<=n;++i) 
		if(d[head][i]+d[i][tail]==d[head][tail]) 
			s[++sn]=i;
	sort(s+1,s+sn+1,cmp);
	// debug 2 
	//for (int i=1;i<=sn;++i) printf("%d\n",s[i]);
	// debug 2 end
	for (int i=1;i<=sn;++i)
		for (int j=i;j<=sn;++j) 
			if(d[s[i]][s[j]]<=S) {
				for (int k=1;k<=n;++k) {
					minn=1000000000;
					for (int l=i;l<=j;++l)
						minn=min(minn,d[k][s[l]]);
					maxx=max(maxx,minn);
				}
				ans=min(ans,maxx);
				maxx=-1;
			}
	printf("%d\n",ans);
	return 0;
}

Noip2012 选择客栈 理论复杂度$O(n^2)$,数据水所以可以过。代码略。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter