社区讨论

谁帮我教一下看看对不对,非常感谢

UVA437巴比伦塔 The Tower of Babylon参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lyo3d8c0
此快照首次捕获于
2024/07/16 15:28
2 年前
此快照最后确认于
2024/07/16 16:12
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int m,cnt;
const int N=1e4;
int idx;
int x[2133],y[2312],w[1231];
int e[N],ne[N],h[N];
int n;
int in[N];
int d[N];
queue<int> q;	
int k,ans;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int f[2312323];//到i 路径中最大权值是多少 
int topsort(){
	queue<int> q;
	for(int i=1;i<=3*n;i++)
	{
		f[i]=w[i];
		if(!in[i]) q.push(i);
	 }
	 while(!q.empty()){
	 	int x=q.front();
	 	ans=max(ans,f[x]);
		q.pop();
	 	for(int i=h[x];i!=-1;i=ne[i]){
	 		int j=e[i];
			in[j]--;
	 		f[j]=max(f[j],f[x]+w[j]);
	 		if(in[j]==0) q.push(j);
		 }
	 }
} 
void solve(){
	idx=0;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>w[i];
		x[i+n]=x[i];
		y[i+n]=w[i];
		w[i+n]=y[i];
		x[i+n*2]=y[i];
		y[i+n*2]=w[i];
		w[i+n*2]=x[i];
	}
	for(int i=1;i<=3*n;i++)
	{
		for(int j=1;j<=3*n;j++)
		if((x[i]<x[j]&&y[i]<y[j])||
		(x[i]<y[j]&&y[i]<x[j])){
			add(i,j);
			in[j]++;
		}
	}
	ans=0;
	topsort();
	cout<<ans<<endl;
	return ;
}
int main(){
	int cnt = 0;
	while(1)
	{
		cin >> n;
		if(n == 0) break;
		cout << "Case " << ++ cnt<< ": maximum height = ";
		solve();
	}
}

回复

1 条回复,欢迎继续交流。

正在加载回复...