Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs的spfa判环

Posted by 70 at 2015-07-10 14:49:18 on Problem 1860
In Reply To:只能优化到32ms?怎么优化到0ms呢...,顺便贴代码 Posted by:xuesu at 2014-07-20 22:31:45
#include <stdio.h>
#include <string.h>
int n, m, s, u[20005], v[20005], first[105], next[20005], cnt;
int sum[101], vis[101], rear, front;
double  r[20005], c[20005], d[101], vv;
struct node{
	int key;
	double mon;
}queue[3005];
void addedge(int st, int ed, double R, double C)
{
	u[++cnt] = st; v[cnt] = ed; r[cnt] = R; c[cnt] = C;
	next[cnt] = first[st];
	first[st] = cnt;
}
int spfa(int s, double k)
{
	int end;
	double money;
	vis[s] = 1;
	for (int i = first[s]; i; i = next[i]) {
		end = v[i];
		if ((d[s] - c[i]) * r[i] > d[end]) {
			d[end] = (d[s] - c[i]) * r[i];
			if (!vis[end]) {
				if (spfa(end, d[end])) return 1;
			}
			else return 1;
		}
	}
	vis[s] = 0;
	return 0;
}
int main()
{
	freopen("1.in", "r", stdin);
	scanf("%d%d%d%lf", &n, &m, &s, &vv);
	int x, y;
	double Rab, Cab, Rba, Cba;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%lf%lf%lf%lf", &x, &y, &Rab, &Cab, &Rba, &Cba);
		addedge(x, y, Rab, Cab);
		addedge(y, x, Rba, Cba);
	}
	memset(d, 0, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[s] = vv;
	if (spfa(s, vv)) printf("YES\n");
	else printf("NO\n");
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator