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