社区讨论

深搜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 条回复,欢迎继续交流。

正在加载回复...