계차 제약 시스템 + spfa 알고리즘 poj 1201

먼저 문 제 를 차분 구속 시스템 으로 전환 한 다음 에 차분 구속 시스템 을 조건 을 만족 시 키 는 그림 으로 전환 한 다음 에 그림 에 대해 최대 (또는 최소) 경 로 를 구한다.
 Dijkstral 과 Bell - man Ford 는 단일 소스 의 최대 최소 경 로 를 구 하 는 방법 입 니 다.하지만 효율 은 높 지 않다.
 spfa (shortest path fast algorithm) 알고리즘 은 효율 이 비교적 높다.거리 가 변 하지 않 는 점 v 에 대해 서 는 앞으로 도 v 를 통 해 다른 점 u 의 경 로 를 변화 시 킬 수 없 기 때문이다.그래서 변 화 된 점 을 기록 하 는 방식 으로 변화 가 없 는 점 은 고려 하지 않 는 다.이 는 Dijkstral 이 매번 모든 정점 이나 Bell - man Ford 를 검사 하 는 것 보다 n - 1 차 효율 이 좋다.
poj 1201 을 하면 서 이런 문 제 를 처음 만 났 습 니 다. 저 는 직관 적 인 욕심 법 으로 풀 었 습 니 다.하지만 효율 은 O (n ^ 2) 입 니 다.
 그리고 차분 구속 시스템 이 왜 그림 의 가장 짧 은 경로 문제 로 바 뀔 수 있 는 지 오랫동안 궁리 한 다음 에 spfa 알고리즘 의 방법 과 실현 을 보 았 다.
 poj 1201 소스 코드:

/*
 * =====================================================================================
 *
 *       Filename:  1201.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2011 12 03  10 32 51 
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  MaZheng (blog.csdn.net/mazheng1989), [email protected]
 *        Company:  Dalian University Of Technology
 *
 * =====================================================================================
 */


#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<queue>
using namespace std;
//please declare parameters here.
const int NUM=50005;
int n;
int low=INT_MAX,high=-1; //

struct Vertex
{
	int v;
	int w;
	Vertex *next;
};
Vertex * Graph[NUM];
int dis[NUM];
bool used[NUM];

//please declare functions here.
void addEdge(int u,int v,int w)
{

	Vertex *ver=new Vertex;
	ver->v=v;
	ver->w=w;
	ver->next=Graph[u];
	Graph[u]=ver;
}
void spfa()
{
   queue<int >Q;
   for(int i=low;i<=high;i++)
   {
	   dis[i]=-INT_MAX;
	   used[i]=false;
   }
   dis[low]=0;
   used[low]=true;
   Q.push(low);
   while(Q.empty()==false)
   {
	   int v=Q.front();
	   Q.pop();
	   used[v]=false;
	   Vertex *p=Graph[v];
	   while(p!=NULL)
	   {
		   int u=p->v;
		   if(dis[v]+p->w>dis[u])
		   {
			   dis[u]=dis[v]+p->w;
			   if(used[u]==false)
			   {
				   Q.push(u);
				   used[u]=true;
			   }
		   }
		   p=p->next;
	   }
   }
   printf("%d
",dis[high]);
}
int main()
{
	freopen("input.txt","r",stdin);
	//input your ...
    int ai,bi,ci;
   	while(scanf("%d",&n)!=EOF)
	{
		low=INT_MAX;
		high=-1;
		memset(Graph,NULL,sizeof(Graph));
		for(int i=0;i<n;i++)
		{
			scanf("%d %d %d",&ai,&bi,&ci);
			if(ai<low)
				low=ai;
			if(bi+1>high)
				high=bi+1;
			addEdge(ai,bi+1,ci);
		}
		for(int i=low;i<=high;i++)
		{
			addEdge(i,i+1,0);
			addEdge(i+1,i,-1);
		}
		spfa();
	}

	return 0;
}