POJ3169 差分约束 线性
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 12522 | Accepted: 6032 |
Description
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
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
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
Hint
There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.
The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.
Source
题意:
我认为题意英文正常的都可以看的懂吧。
就是奶牛排队,一个地方可以容纳许多奶牛,
奶牛有互相喜欢的和互相讨厌的,
先输入喜欢的,1号3号相互喜欢,距离不能超过10
2和4不能超过20,2,3不能小于3
对于喜欢输入A,B,C
就是说d[B]-d[A]<=C;
转化为,d[B]<=C+d[A];
求最多,用最短路,下面也需要化成形式一致的才可以。
不能忘了d[i]-d[i-1]>=0这个限制。
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#define INF 2000000007
#define N 1007
#define M 10007
using namespace std; int n,l,r;
int dis[N],num[N],ins[N];
int cnt,head[N],next[M*],rea[M*],val[M*]; void add(int u,int v,int fee)
{
next[++cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
val[cnt]=fee;
}
bool Spfa()
{
for (int i=;i<=n;i++)
ins[i]=,dis[i]=INF,num[i]=;
queue<int>q;
q.push();dis[]=,num[]=;
while(!q.empty())
{
int u=q.front();q.pop();
for (int i=head[u];i!=-;i=next[i])
{
int v=rea[i],fee=val[i];
if (dis[v]>dis[u]+fee)
{
dis[v]=dis[u]+fee;
if (!ins[v])
{
num[v]++;
ins[v]=;
q.push(v);
if (num[v]>n) return false;
}
}
}
ins[u]=;
}
return true;
}
int main()
{
memset(head,-,sizeof(head));
scanf("%d%d%d",&n,&l,&r);
for (int i=,x,y,z;i<=l;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for (int i=,x,y,z;i<=r;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(y,x,-z);
}
for (int i=;i<=n;i++)
add(i+,i,);
bool flag=Spfa();
if (!flag) printf("-1\n");
else
{
if (dis[n]==INF) printf("-2\n");
else printf("%d\n",dis[n]);
}
}
最新文章
- Chinese economic influence in North Korea
- WPF中查看PDF文件
- System.ArgumentOutOfRangeException: 指定的参数已超出有效值的范围
- 4. Android框架和工具之 android-async-http
- mysql_create_frm
- 【HDOJ】4261 Estimation
- Big ball of Mud
- Atom打造 c/c++编译环境(忙了一个上午)
- CentOS自带mysql配置(密码更改、端口开放访问、添加进系统启动项)
- samba的安装和配置
- java 删除整数元素集合中的元素
- LeetCode(100):相同的树
- python-批量添加图片水印
- Implement strStr() leetcode java
- ant 标签详解
- bzoj3029 守卫者的挑战 (多维dp)
- 使用Docfx生成项目文档
- QT For Android 运行的时候找不到手机怎么办?
- 简述负载均衡和CDN技术
- [PHP] apache在worker模式配置fastcgi使用php-fpm
热门文章
- 转 SQL*PLUS中的替换变量(&; &;&;)
- 206 Reverse Linked List 反转链表
- LD_LIBRARY_PATH与-L的关系以及延伸
- C# KeepAlive的设置
- Windows远程桌面连接复制文件失败或非常慢
- EL表达式、JSTL
- contact用法解析
- OC中文件读取类(NSFileHandle)介绍和常用使用方法
- Linux 时间同步 ntpdate
- Farseer.net轻量级ORM开源框架 V1.2.1版本升级消息