Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课《ACM/ICPC竞赛训练》面向全球招生!

spfa防自环(货币自己换自己价值升高的情况)

Posted by liaopifan at 2017-09-12 20:31:39 on Problem 2240
bool spfa(){
	memset(in,0,sizeof(in));
	memset(vis,0,sizeof(vis));
	fill(d+1,d+1+n,-1.0);
	while(!q.empty()) q.pop();
	vis[1]=1;
	d[1]=1;//设定初始拥有钱数为1; 
	q.push(1);
	while(!q.empty()){
		int t = q.front();
		vis[t] = 0;//防止自环导致的错误,去掉后wa 
		for(int i=1;i<=n;i++){
			if(d[t]!=-1 && map[t][i]!=-1 && d[t]*map[t][i] > d[i]){
			//	debug(i);debug(t);debug(d[i]);debug(d[t]*map[t][i]);
				d[i] = d[t]*map[t][i];				
				if(!vis[i]){
					q.push(i);
					vis[i] = 1;
					in[i]++;
					if(in[i]>n){
						return true;
					}					
				}
			}
		}
		vis[t] = 0;
		q.pop();
	}
	return false;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator