poj 3169 Layout(差分约束)
2024-09-30 07:39:20
Layout
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6549 | Accepted: 3168 |
Description
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they
can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).
Some cows 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 ML (1 <= ML <= 10,000) constraints describes which cows like each other
and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows 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 cow 1 and cow N that satisfies the distance constraints.
can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).
Some cows 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 ML (1 <= ML <= 10,000) constraints describes which cows like each other
and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows 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 cow 1 and cow N that satisfies the distance constraints.
Input
Line 1: Three space-separated integers: N, ML, and MD.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
解题思路:
1、构造差分约束系统:
A。B距离不超过D则B-A<=D,
A,B距离至少为D则A-B<=-D.
2、若有解则求1和N之间的最短路径:
比如:A-B<=D1 , B-C<=D2, A-C<=D3 不等式相加得:A-C<=min(D3,D1+D2)。而当A-B<=D时。我们建的边是B->A的。所以我们仅仅要求出1到N的最短距离就可以,假设没有最短距离。则输出-2.
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std; const int maxne = 1000000;
const int maxnn = 1010;
const int INF = 0x3f3f3f3f;
struct edge{
int u , v , d;
edge(int a = 0 , int b = 0 , int c = 0){
u = a , v = b , d = c;
}
}e[maxne];
int head[maxnn] , next[maxne] , cnt , dis[maxnn] , vis[maxnn] , vt[maxnn];
int N , ML , MD; void add(int u , int v , int d){
e[cnt] = edge(u , v , d);
next[cnt] = head[u];
head[u] = cnt++;
} void initial(){
for(int i = 0; i < maxnn; i++) head[i] = -1 , dis[i] = INF , vis[i] = 0 , vt[i] = 0;
for(int i = 0; i < maxne; i++) next[i] = -1;
cnt = 0;
for(int i = 1; i < N; i++){
add(0 , i , 0);
add(i+1 , i , 0);
}
add(0 , N , 0);
dis[0] = 0;
} void readcase(){
int u , v , d;
while(ML--){
scanf("%d%d%d" , &u , &v , &d);
add(u , v , d);
}
while(MD--){
scanf("%d%d%d" , &u , &v , &d);
add(v , u , -1*d);
}
} bool SPFA(int start){
queue<int> q;
q.push(start);
vt[start]++;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
int n = head[u];
if(vt[u] > N+1){
return false;
}
while(n != -1){
int v = e[n].v;
if(dis[v] > dis[u]+e[n].d){
dis[v] = dis[u]+e[n].d;
if(vis[v] == 0){
vt[v]++;
q.push(v);
vis[v] = 1;
}
}
n = next[n];
}
}
return true;
} void computing(){
if(!SPFA(0)){
printf("-1\n");
}else{
for(int i = 0; i < maxnn; i++) dis[i] = INF;
dis[1] = 0;
SPFA(1);
if(dis[N] == INF){
printf("-2\n");
}else{
printf("%d\n" , dis[N]);
}
}
} int main(){
while(scanf("%d%d%d" , &N , &ML , &MD) != EOF){
initial();
readcase();
computing();
}
return 0;
}
最新文章
- Web前端需要熟悉大学里【高大上】的计算机专业课吗?
- 1.系统生命开发周期(SDLC)
- 轻型的ORM类Dapper
- python模块
- 记录下ECharts的一些功能
- Rhel6-DM多路经存储配置文档
- VS/Visual studio 源代码编辑器里的空处出现点号解决办法
- [置顶] 单键模式的C++描述
- php的redis的pconnect
- 实现定时备份mysql数据库并把备份数据库邮件发送
- spring-core 中 asm 包的作用
- Eureka 参数调优
- Java内部类详解(一)
- Java——HashMap
- java 强制转换之降级
- js 函数参数 arguments[0]
- java中的变量和常量
- qemu网络虚拟化之数据流向分析三
- 从零玩转JavaWeb系列7web服务器-----get与post的区别
- 霍金:AI或许能根除疾病和贫穷,但也可能摧毁人类 | GMIC 2017