社区讨论

交了那么多次都Unknown,有没有路过的大佬帮看下代码思路有问题吗

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lzwviacj
此快照首次捕获于
2024/08/16 23:37
2 年前
此快照最后确认于
2024/08/17 10:37
2 年前
查看原帖
建图+最长路
CPP
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define int long long
#define ll long long
using namespace std;
const int maxn=5e4;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int cnt=0,n,cnta=0;
struct point
{
	ll x,y,h;
}a[maxn];
bool compare(point &a,point &b)
{
	return (a.x>b.x&&a.y>b.y)||(a.y>b.x&&a.x>b.y);
}
void addp(ll x,ll y,ll h)
{
	a[cnta].x=x;
	a[cnta].y=y;
	a[cnta++].h=h;
}
struct Edge
{
	int v,next;ll w;
}e[maxn*2];
int head[maxn*2];
void add(int u,int v,ll w)
{
	e[++cnt].w=w;
	e[cnt].next=head[u];
	e[cnt].v=v;
	head[u]=cnt;
}
ll dis[maxn];
bool vis[maxn];
void dfs(int s)
{
	mem(dis,0);
	mem(vis,0);
	queue<int> q;
	q.push(s),vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].v;ll w=e[i].w;
			if(dis[v]<dis[u]+w) 
			{
				dis[v]=dis[u]+w;
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
	}
}
void make()
{
	for(int i=0;i<cnta;i++)
	{
		for(int j=0;j<cnta;j++)
		{
			if(compare(a[i],a[j])) add(i,j,a[j].h);
		}
		add(cnta,i,a[i].h);
		add(i,cnta+1,0);
	}
}
signed main()
{
	n=read();
	while(n)
	{
		for(int i=0;i<n;i++)
		{
			ll x=read(),y=read(),z=read();
			addp(x,y,z);addp(x,z,y);addp(y,z,x);
		}
		make();
		dfs(cnta);
		cout<<"Case i: maximum height = "<<dis[cnta+1]<<"\n";
		cnt=0,cnta=0;
		mem(head,0);
		n=read();
	}
}
a数组用于暂存点,cnta是统计a的数量,addp是加点,其他就是模版了
话说有没有大佬知道怎么解决unknown吗,快炸了

回复

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

正在加载回复...