poj1860 解题报告

题意：这里有N种货币，分别记为1~N，有M种货币交换的方式，每一种方式有A，B两种钱币，有R, C, R and CNick手上有其中的一种货币S，货币S的钱数为V，问你能否通过一定次数的钱币交换让Nick手中的钱增加

分析：

这里是要判断回路，那么可以用spfa 加一个入队次数的数组来判别是否有回路，也可以用bellman，这里要注意的是，松弛操作不能死用模板了，， 要有一点点的转变，这里我们可以这样处理，置 d 这个松弛要用到的数组为0，不是以往的无穷大，新加一个入队数组判回路 cnt 为0

那么直接上马，附加注释

// AC 204k 32ms

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define MAX 101

struct node

{

	int to;

	double r,c;

	int next;

}edge[MAX*2];

int head[MAX],tol;

int N,M,S;

double V;

void add(int st,int end,double r,double c)

{

	edge[tol].to = end;

	edge[tol].r = r;

	edge[tol].c  =c;

	edge[tol].next = head[st];

	head[st] = tol++;

}

void init()

{

	int i;

	for(i = 1 ; i <= N ; i ++) head[i] = -1;

	tol = 0;

	int a,b;

	double c,d;

	for(i = 0 ; i < M ; i ++)

	{

		scanf("%d%d%lf%lf",&a,&b,&c,&d);

		add(a,b,c,d);

		scanf("%lf%lf",&c,&d);

		add(b,a,c,d);

	}

}

double d[MAX];

int cnt[MAX];//记录入队次数

bool flag[MAX];

bool spfa()

{

	int i;

	for(i = 1 ; i <= N ; i ++) flag[i] = false,d[i] = 0,cnt[i] = 0;

	d[S] = V;//我们这里把初始的d 置为 V，也就是现有的钱数，

	queue<int>q;

	q.push(S);

	cnt[S]++;

	while(!q.empty())

	{

		int u=q.front();q.pop();flag[u]=false;

		for(int j = head[u] ; j != -1 ; j = edge[j].next)

		{

			int v = edge[j].to;

			double r = edge[j].r, c = edge[j].c;

			if(d[v] < (d[u]-c)*r)//这里就是需要转变一点点的松弛操作

			{

				d[v] = (d[u]-c)*r;

				if(!flag[v])

					flag[v] = true,cnt[v] ++,q.push(v);

				if(cnt[v] > N) //如果入队次数大于点数，那么就是有回路

					return true;

			}

		}

	}

	return false;

}

int main()

{

	scanf("%d%d%d%lf",&N,&M,&S,&V);

	init();

	if(spfa())

		printf("YES\n");

	else

		printf("NO\n");

	return 0;

}

个人愚昧观点 ，欢迎指正与讨论