POJ-3169-Layout，HDU-3592-World Exhibition（线性约束，板子）

题目链接：http://poj.org/problem?id=3169

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3592

题目大意：n头牛，编号1~n，给出ml个关系（牛与牛之间最大的距离）md个关系（牛与牛之间最小的距离），编号小的总在编号大的前面（可以站在一起），问，牛1到牛n的最远距离是多少。无解输出-1，无穷解输出-2，正解输出dis

HDU的题跟这个一个意思，输入都是一个意思。，代码都不用改，加个Case组输入就行了。

思路：如标题所示，线性约束的板子，题上说的很明确，输入数据a<b，所以前面的那个数就是小号，直接建立图，注意题中的一个隐含条件，即：d[i-1]-d[i]<=0也要加上，虽然不加也能A，但是是错的，讨论区的一些dalao给的样例过不去，网上很多人的代码有问题。

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include<stdio.h>
#include<string.h> 
#include<math.h> 
   
#include<map>  
//#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
#define ll long long 
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);

struct node{
	int v,val,nxt;
	node(int _v=0,int _val=0,int _nxt=0){
		v=_v;val=_val;nxt=_nxt;
	}
}edge[MAXN<<4];
int head[MAXN],ecnt;
int st[MAXN],tot;
int dis[MAXN],vis[MAXN],sum[MAXN];
int n,ml,md,flag;

void intt(){
	clean(head,-1);
	ecnt=0;tot=0;
}
void add(int u,int v,int val){
	edge[ecnt]=node(v,val,head[u]);
	head[u]=ecnt++;
//	edge[ecnt]=node(u,val,head[v]);
//	head[v]=ecnt++;
}
void dfs_spfa(){
	clean(dis,INF32);dis[1]=0;
	clean(vis,0);vis[1]=1;
	clean(sum,0);sum[1]++;
	st[tot++]=1;
	while(tot){
		int u=st[--tot];vis[u]=0;
		//cout<<u<<" : "<<dis[u]<<endl;
		for(int i=head[u];i+1;i=edge[i].nxt){
			int v=edge[i].v;
			if(dis[v]>dis[u]+edge[i].val){
				dis[v]=dis[u]+edge[i].val;
				//cout<<v<<" ";
				if(vis[v]==0){
					vis[v]=1;
					st[tot++]=v;
					sum[v]++;
					if(sum[v]>=n){
						flag=1;return ;
					}
				}
			}
		}
	}
}
int main(){
	while(~scanf("%d%d%d",&n,&ml,&md)){
		intt();
		int a,b,val;
		for(int i=1;i<=ml;++i){
			scanf("%d%d%d",&a,&b,&val);
			add(a,b,val);
		}
		for(int i=1;i<=md;++i){
			scanf("%d%d%d",&a,&b,&val);
			add(b,a,-val);
		}flag=0;
		for(int i=2;i<=n;++i){
			add(i,i-1,0);
		}
		dfs_spfa();
		if(flag){//存在负环 
			printf("-1\n");
		}
		else{
			if(dis[n]==INF32){
				printf("-2\n");
			}
			else{
				printf("%d\n",dis[n]);
			}
		}
	}
}
/*
3 2 1
1 2 5
1 3 10
2 3 20
这个数据应该输出 -1
4 2 1
1 3 10
2 4 10
2 4 2
这个数据应该输出 20
*/