| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
G++ WA C++ AC 这不科学(附代码)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator