社区讨论
深搜RE了
P1931套利参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m5yu4iha
- 此快照首次捕获于
- 2025/01/16 12:32 去年
- 此快照最后确认于
- 2025/11/04 11:32 4 个月前
样例过了,用深搜做的,主要是看这数据量觉得深搜应该问题不大,但就是不知道为啥会RE
CPP#include<bits/stdc++.h>
#include<map>
using namespace std;
struct st
{
int from,to,next;
double w;
}e[100000];
int h[301],cnt;
double w[301];
void add(int u,int v,double w)
{
e[cnt].from=u;
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=h[u];
h[u]=cnt;
cnt++;
}
void dfs(int k,int b)
{
int i;
if(k==b && w[k]>1)
return; //确定能套利,会一直循环下载重复套的
for(i=h[k];i;i=e[i].next)
if(w[e[i].to]<w[e[i].from]*e[i].w)
{
w[e[i].to]=w[e[i].from]*e[i].w;
dfs(e[i].to,b);
}
}
int main()
{
int k;
for(k=1;;k++)
{
int n,i,j;
double x;
bool ans=false;
string s,t;
cin>>n;
if(n==0)
break;
map<string,int>a;
for(i=1;i<=n;i++)
{
cin>>s;
a[s]=i;
h[i]=0;
}
cnt=1;
cin>>n;
for(i=0;i<n;i++)
{
cin>>s>>x>>t;
add(a[s],a[t],x);
}
for(i=1;i<=n;i++)
{
for(j=0;j<=30;j++)
w[j]=0;
w[i]=1;
dfs(i,i);
if(w[i]>1)
{
ans=true;
break;
}
}
if(ans)
cout<<"Case "<<k<<": Yes\n";
else
cout<<"Case "<<k<<": No\n";
a.clear();
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...