【题目大意】
n头牛从小到大排,它们之间某些距离不能大于一个值,某些距离不能小于一个值,求第一头牛和第N头牛之间距离的最大值。
【思路】
由题意可以得到以下不等式d[AL]+DL≥d[BL];d[BD]+(-DD)≥d[AD];d[i+1]+0≥d[i],显然是差分约束系统。即构造从AL到BL权值为DL的边,从BD到AD构造权值为-DD的负边,从i+1到i构造权值为0的边。最后求最短路径。安利一个证明(点我)。
对于差分约束系统要注意的是,如果要求最大距离,用最短路径;求最小距离,用最长路径,要根据实际情况判断。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=+;
struct Rec
{
int ori,des,len;
};
int n,ml,md;
int first[MAXN/],next[MAXN*+];
Rec edge[MAXN*+];
int vis[MAXN/],dis[MAXN/],appear[MAXN/]; void init()
{
memset(first,-,sizeof(first));
scanf("%d%d%d",&n,&ml,&md);
int j=-;
for (int i=;i<ml;i++)
{
j++;
scanf("%d%d%d",&edge[j].ori,&edge[j].des,&edge[j].len);
edge[j].ori--;edge[j].des--;
next[j]=first[edge[j].ori];
first[edge[j].ori]=j;
}
for (int i=;i<md;i++)
{
j++;
scanf("%d%d%d",&edge[j].des,&edge[j].ori,&edge[j].len);
edge[j].ori--;edge[j].des--;
edge[j].len=-edge[j].len;
next[j]=first[edge[j].ori];
first[edge[j].ori]=j;
}
for (int i=;i<n;i++)
{
j++;
edge[j].ori=i;edge[j].des=i-;edge[j].len=;
next[j]=first[edge[j].ori];
first[edge[j].ori]=j;
}
} void SPFA()
{
queue<int> que;
memset(vis,,sizeof(vis));
memset(appear,,sizeof(appear));
for (int i=;i<n;i++) dis[i]=0x7fffffff;
dis[]=;
que.push();
vis[]=;
appear[]++; while (!que.empty())
{
int head=que.front();
int k=first[head];
while (k!=-)
{
Rec e=edge[k];
if (dis[e.des]>dis[e.ori]+e.len)
{
dis[e.des]=dis[e.ori]+e.len;
if (!vis[e.des])
{
appear[e.des]++;
if (appear[e.des]>n)
{
cout<<-<<endl;
return;
}
que.push(e.des);
vis[e.des]=;
}
}
k=next[k];
}
vis[head]=;
que.pop();
}
if (dis[n-]==0x7fffffff) cout<<-<<endl; else cout<<dis[n-]<<endl;
} int main()
{
init();
SPFA();
system("pause");
return ;
}