社区讨论
交了那么多次都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 条回复,欢迎继续交流。
正在加载回复...