Layout( 差分约束\(\star \))
- 时限:\(1s\) 内存:\(256M\)
Descrption
- 和人类一样,奶牛们在打饭的时候喜欢和朋友站得很近。
- 约翰的编号为 \(1\) 到 \(n\) 的 \(n(2<=n<=1000)\) 只奶牛正打算排队打饭。现在请你来安排她们,让她们在数轴上排好队。奶牛的弹性很好,同一个坐标可以站无限只奶牛,排队的顺序必须和她们编号的顺序一致。有 \(M\) 对奶牛互相爱慕,她们之间的距离不能超过一定的值,有 \(K\) 对奶牛互相敌视,她们的距离不能小于一定的值。
- 那么,首尾奶牛的最大距离是多少呢?
Input
- 第一行输入 \(n,M,K, (0<M,K<=5000)\) 。
- 接下来 \(M\) 行每行三个整数\(x,y,z\),表示编号为 \(x\) 和 \(y\) 的两头奶牛之间的距离最大不超过 \(z\)。
- 再接下来 \(K\) 行每行三个整数 \(a,b,c\),表示编号为 \(a\) 和 \(b\) 的两头奶牛之间的距离最少为\(c\)。
Output
- 如果没有合理方案,输出 \(-1\),如果首尾两头牛的距离可以无限大,输出 \(-2\),否则输出一个整数表示首尾奶牛的最大距离。
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
Hint
- 四只牛分别在 \(0,7,10,27\)。
- 来源:\(luogu4878\)
分析
- 基础差分约束,如果遗忘,大家请复习:差分约束
Code
#include <bits/stdc++.h>
const int maxn=1e3+5,maxm=2e4+5,Inf=0x3f3f3f3f;
struct Node{
int to,w,next;
}e[maxm];
int n,len,head[maxn];
int dis[maxn],vis[maxn],cnt[maxn];
void Insert(int u,int v,int w){
e[++len].to=v;e[len].w=w;e[len].next=head[u];head[u]=len;
}
int Spfa(int x){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
std::queue<int> q;
dis[x]=0;q.push(x);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;q.push(v);
cnt[v]++;
if(cnt[v]>n)return -1;
}
}
}
}
if(dis[n]==Inf)return -2;
return dis[n];
}
void Solve(){
int M,K;scanf("%d%d%d",&n,&M,&K);
int u,v,w;
memset(head,-1,sizeof(head));
for(int i=1;i<=M;++i){
scanf("%d%d%d",&u,&v,&w);
if(u>v)std::swap(u,v);//从序号低的点向序号大的点建边
Insert(u,v,w);
}
for(int i=1;i<=K;++i){
scanf("%d%d%d",&u,&v,&w);
if(u>v)std::swap(u,v);
Insert(v,u,-w);//从高序号到低序号建负边
}
for(int i=1;i<n;++i)//牛必须按顺序站所以必须建相邻边
Insert(i+1,i,0);
for(int i=1;i<=n;++i)
Insert(0,i,0);
if(Spfa(0)==-1){
printf("-1\n");return;
}
printf("%d\n",Spfa(1));
}
int main() {
Solve();
return 0;
}
/*
4 1 1
1 4 10
2 3 20
-------
-1
*/
原文链接: https://www.cnblogs.com/hbhszxyb/p/13321821.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/366993
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!