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

再写一次,还是不太理解这题常规条件的处理问题,能够帮忙解释下吗?

Posted by tzzhwj at 2008-11-15 19:17:28 on Problem 1201
其实如何构图来解决这个问题和为什么用bellmanford解决这个问题我都十分明白了,就是不明白下面列出的一个问题,希望知道的帮忙解答下啊,谢谢!

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAX 60000
#define MAXINT 1000000

struct EDGE
{
	int st,ed,val;
}edge[MAX];

int dis[MAX],n,min,max;

int bellman_ford()
{
	int i,k;

	for(i=min;i<=max;i++)
		dis[i]=-MAXINT;

	dis[min]=0;

	bool over;

	for(k=0;k<=max-min;k++)
	{
		over=true;

		for(i=0;i<n;i++)
			if(dis[edge[i].st]!=-MAXINT&&dis[edge[i].st]+edge[i].val>dis[edge[i].ed])
			{
				dis[edge[i].ed]=dis[edge[i].st]+edge[i].val;
				over=false;
			}

			for(i=min;i<max;i++)
				if(dis[i]!=-MAXINT&&dis[i]>dis[i+1])
				{
					dis[i+1]=dis[i];
					over=false;
				}

				for(i=max;i>min;i--)
					if(dis[i]!=-MAXINT&&dis[i]-1>dis[i-1])
					{
						dis[i-1]=dis[i]-1;
						over=false;
					}
					if(over)
						break;
	}

	return dis[max];
}

int main()
{
	int i;

	while(scanf("%d",&n)!=EOF)
	{
		min=MAXINT;
		max=0;

		for(i=max;i<n;i++)
		{
			scanf("%d%d%d",&edge[i].st,&edge[i].ed,&edge[i].val);

			edge[i].ed++;

			if(edge[i].ed>max)
				max=edge[i].ed;
			if(edge[i].st<min)
				min=edge[i].st;
		}

		printf("%d\n",bellman_ford());
	}

	return 0;
}

这是晚上的代码,其中下面这段代码是为了解决
对于自然数x,有0 < = F(x+1) - F(x) <= 1,即F(x+1) - F(x) <= 1 && F(x) - F(x+1) <= 0 这个常规约束条件的。不明白为什么要一个升序,一个降序来更新数据,大家都升序来更新不可以吗?希望能指导一下我啊,谢谢!

for(i=min;i<max;i++)
				if(dis[i]!=-MAXINT&&dis[i]>dis[i+1])
				{
					dis[i+1]=dis[i];
					over=false;
				}

				for(i=max;i>min;i--)
					if(dis[i]!=-MAXINT&&dis[i]-1>dis[i-1])
					{
						dis[i-1]=dis[i]-1;
						over=false;
					}



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