pku 1860 Currency Exchange
题意：第一行：货币的总的种类，货币中心的数量，所持有的货币种类，持有该种类货币的数量
后M行：货币a，货币b，汇率Rab， 手续费Cab， 汇率Rba， 手续费Cba
思路：用spfa找到，看是否有负权回路（用count[]计数，记录每个结点进队次数，超过|n|次表示有负权），如果有，则表示可以一直增加自己的钱，用bellman也可以实现
虽然是A了，感觉数据挺弱……
比较郁闷的是小号交47ms，大号交79ms - -|||
调了很久，最后很没脾气的加了eps，然后没有编译直接小号交了，居然A了……
code：
#include <iostream>
#include <cstdio>
#include <climits>
#include <queue>
#include <cstring>
#define eps 1e-6
using namespace std;
const int MAXN=105;
int m, n, type;
double money;
struct Node
{
double r, c;
}map;
int count;
bool spfa(int s, int e)
{
queue<int> q;
double dist;
bool vis;
memset(vis, 0, sizeof(vis));
memset(count, 0, sizeof(count));
for(int i=1; i<=n; i++)
dist=0;
dist=money;
vis=1;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
if(count>n) return 0;
vis=0;
for(int i=1; i<=n; i++)
if((dist-map.c)*map.r>dist+eps)
{
dist=(dist-map.c)*map.r;
if(!vis)
{
vis=1;
q.push(i);
count++;
}
}
}
return 1;
}
int main()
{
while(scanf("%d%d%d%lf", &n, &m, &type, &money)!=EOF)
{
for(int i=0; i<m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
scanf("%lf%lf%lf%lf", &map.r, &map.c, &map.r, &map.c);
}
int flag;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
flag=spfa(j, i);
if(!flag) break;
}
}
if(!flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
页:
[1]