首页 > ACM题库 > HDU-杭电 > HDU 3592-World Exhibition-最短路径-[解题报告]HOJ
2014
11-27

HDU 3592-World Exhibition-最短路径-[解题报告]HOJ

World Exhibition

问题描述 :

Nowadays, many people want to go to Shanghai to visit the World Exhibition. So there are always a lot of people who are standing along a straight line waiting for entering. Assume that there are N (2 <= N <= 1,000) people numbered 1..N who are standing in the same order as they are numbered. It is possible that two or more person line up at exactly the same location in the condition that those visit it in a group.

There is something interesting. Some like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of X (1 <= X <= 10,000) constraints describes which person like each other and the maximum distance by which they may be separated; a subsequent list of Y constraints (1 <= Y <= 10,000) tells which person dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between person 1 and person N that satisfies the distance constraints.

输入:

First line: An integer T represents the case of test.

The next line: Three space-separated integers: N, X, and Y.

The next X lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= N. Person A and B must be at most C (1 <= C <= 1,000,000) apart.

The next Y lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= C. Person A and B must be at least C (1 <= C <= 1,000,000) apart.

输出:

First line: An integer T represents the case of test.

The next line: Three space-separated integers: N, X, and Y.

The next X lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= N. Person A and B must be at most C (1 <= C <= 1,000,000) apart.

The next Y lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= C. Person A and B must be at least C (1 <= C <= 1,000,000) apart.

样例输入:

1
4 2 1
1 3 8
2 4 15
2 3 4

样例输出:

19

http://poj.org/problem?id=3169

http://acm.hdu.edu.cn/showproblem.php?pid=3592

题目大意:

一些母牛按序号排成一条直线。有两种要求,A和B距离不得超过X,还有一种是C和D距离不得少于Y,问可能的最大距离。如果没有输出-1,如果可以随便排输出-2,否则输出最大的距离。

思路:

对于第一种

A-B <=X

第二种有

C-D>=Y也就是  D-C<=Y

还有就是题目要求的是按照序号升序排。

然后又不等式3 :  S[ i ] – S[ i-1 ] >=0    也就是 S[ i-1 ] - S[ i ]<=0    

还有就是要求最短路。

建完图后SPFA即可。(有负环说明无解输出-1 , 1与n不连通说明可以随意摆放,没有约束嘛。输出-2,否则输出dis [n])

PS:差分约束还剩两题,等下去刷完写个总结~

在PS:HDU的这题只是输入改一下而已。。。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000+10;
const int MAXM=200000+1000;
const int INF=100000000;
struct edge
{
	int to;
	int val;
	int next;
}e[MAXM];
int head[MAXN],dis[MAXN],len,n,ml,md;

void add(int from,int to,int val)
{
	e[len].to=to;
	e[len].val=val;
	e[len].next=head[from];
	head[from]=len++;
}

int spfa()
{
	int start=1;
	bool vis[MAXN]={0};
	int cnt[MAXN]={0};
	deque<int> q;
	q.push_back(start);
	vis[start]=1;
	cnt[start]=1;
	dis[start]=0;
	while(!q.empty())
	{
		int cur=q.front();
		q.pop_front();
		vis[cur]=false;
		for(int i=head[cur];i!=-1;i=e[i].next)
		{
			int id=e[i].to;
			if(dis[id] > dis[cur] + e[i].val)
			{
				dis[id]=dis[cur] + e[i].val;
				if(!vis[id])
				{
					if(++cnt[id] > n)
						return -1;
					vis[id]=true;
					if(!q.empty() && dis[id] > dis[q.front()]) 
						q.push_back(id);
					else
						q.push_front(id);
				}
			}
		}
	}

	if(dis[n]==INF)
		return -2;
	
	return dis[n];
}

int main()
{
	while(~scanf("%d%d%d",&n,&ml,&md))
	{
		memset(head,-1,sizeof(head));
		len=0;
		for(int i=1;i<=n;i++)
		{
			dis[i]=INF;
			add(i,i-1,0);
		}

		for(int i=0;i<ml;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(from,to,val);	
		}
		
		for(int i=0;i<md;i++)
		{
			int from,to,val;
			scanf("%d%d%d",&from,&to,&val);
			add(to,from,-val);	
		}


		printf("%d\n",spfa());
		
	}
	return 0;
}

参考:http://blog.csdn.net/murmured/article/details/18819955


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept