POJ 3169 Layout 差分约束

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

题目大意:

一些母牛按序号排成一条直线。有两种要求,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:差分约束还剩两题,等下去刷完写个总结~

#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;
}


POJ 3169 Layout 差分约束

上一篇:类对象内存布局,虚函数,虚拟继承和多重继承的实现


下一篇:使用FreeMarker生成Word出错的一点心得