【題目鏈接】:http://poj.org/problem?id=1860
【題意】
給你n種貨幣,m種貨幣之間的交換信息;
交換信息以
A,B,RA,CA,RB,CB的形式給出;
即A換B的話假設A有x元則換成B就變成(X-CA)*RA
B換成A的話同理;
然后你一開始只有某一種x貨幣;
問你可不可能通過換貨幣來獲得更多x貨幣;
即最后又要換回來.
【題解】
可以在做SPFA的最長路的時候判斷能不能出現環.
具體的。
只要從x出去了,然后又回來了;
就說明能夠在經過某些路徑之后這個x又變大了;
任意哪一個x都可以;
因為你可以通過這條路徑讓x變得無窮大;
那么起點s肯定也能無窮大啦;
判斷環的話只要判斷一個點是否入隊n次就好;
【Number Of WA】
1
【完整代碼】
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;struct abc
{int en;double r,c;
};int n,m,s,num[N];
bool inq[N];
double dis[N];
vector <abc> G[N];
queue <int> dl;int main()
{//freopen("F:\\rush.txt","r",stdin);memset(dis,-INF,sizeof dis);cin >> n >> m >> s;cin >> dis[s];for (int i = 1;i <= m;i++){int x,y;double r,c;abc temp;cin >>x >> y >> r >> c;temp.r = r,temp.c = c,temp.en = y;G[x].push_back(temp);cin >> r >> c;temp.r = r,temp.c = c,temp.en = x;G[y].push_back(temp);}dl.push(s);num[s]=1;inq[s] = true;while (!dl.empty()){int x = dl.front();inq[x] = false;dl.pop();int len = G[x].size();for (int i = 0;i <= len-1;i++){abc temp1 = G[x][i];int y = temp1.en;double ju = (dis[x]-temp1.c)*temp1.r;if (ju>0){if (dis[y]<ju){dis[y] = ju;if (!inq[y]){num[y]++;if (num[y]>n)return cout <<"YES"<<endl,0;dl.push(y);inq[y]=true;}}}}}cout <<"NO"<<endl;return 0;
}
