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

G++ WA C++ AC 这不科学(附代码)

Posted by liaoyuhao at 2013-04-09 20:22:19 on Problem 1860
#include<iostream>
#include<string.h>
#define eps 1e-8
using namespace std;
//最初的货币序号, n种货币(n个点), m个兑换点(一共2m条边,但是这里没用这个性质,用的邻接表的结构处理的边数)
int s, n, m;
double v;	//最初拥有的钱

const int MAX = 500;
struct
{
	//到哪个顶点
	int to;
	//计算权值需要的值
	double rate, cost;
	//这个顶点的下一条边的序号
	int next;
}Edge[MAX];
//pre[i] 的值表示 i 顶点的第一条边的序号 即:	Edge[pre[i]] 就是 i 顶点的第一条边
int pre[MAX];
//记录原点到每个点后的数量
double dis[MAX];
//bellman_frod 算法
bool bellman_frod()
{
	//这里要判断的是正环,所以有些变化
	memset(dis, 0, sizeof(dis));
	int p;			//算法执行开始及循环的点
	bool flag;		//松弛的标记,是否进行了松弛
	dis[s] = v;		//s为原点,因为持有 s 货币
	//执行 顶点数 - 1 次循环
	for(int i = 1; i < n; ++i)
	{
		flag = false;	
		for(int j = 1; j <= n; ++j)
		{
			p = pre[j];
			while(true)
			{			
				//TODO 松弛操作
				if(dis[Edge[p].to] < (dis[j] - Edge[p].cost) * Edge[p].rate - eps)
				{
					dis[Edge[p].to] = (dis[j] - Edge[p].cost) * Edge[p].rate;
					flag = true;
				}
				if(Edge[p].next == -1)	break;
				p = Edge[p].next;
			}
		}
		if(!flag)	break;
	}
	//检查是否有正环(如果还能松弛就有)
	for(int i = 1; i < n; ++i)
	{
		p = pre[i];
		while(true)
		{
			if(dis[Edge[p].to] < (dis[i] - Edge[p].cost) * Edge[p].rate)
				return false;
			if(Edge[p].next == -1)	break;
			p = Edge[p].next;
		}
	}
	return true;
}

int main()
{
	int i = 0;
	cin >> n >> m >> s >> v;
	int from, to;
	double ratex, costx, ratey, costy;
	//初始化 pre
	memset(pre, -1, sizeof(pre));
	//初始化邻接表
	while(m--)
	{
		cin >> from >> to >> ratex >> costx >> ratey >> costy;
		Edge[i].to = to;	Edge[i].rate = ratex;	Edge[i].cost = costx;	Edge[i].next = pre[from];	pre[from] = i;	++i;
		Edge[i].to = from;	Edge[i].rate = ratey;	Edge[i].cost = costy;	Edge[i].next = pre[to];		pre[to] = i;	++i;
	}
	if(bellman_frod())
		cout << "NO" << endl;
	else
		cout << "YES" << endl;
	return 0;
}

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