POJ——3169Layout(差分约束)
POJ——3169Layout
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 14702 | Accepted: 7071 |
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
题目大意:
n头牛编号为1到n,按照编号的顺序排成一列,每两头牛的之间的距离 >= 0。这些牛的距离存在着一些约束关系:
1.有ml组(u, v, w)的约束关系,表示牛[u]和牛[v]之间的距离必须 <= w。
2.有md组(u, v, w)的约束关系,表示牛[u]和牛[v]之间的距离必须 >= w。
问如果这n头无法排成队伍,则输出-1,如果牛[1]和牛[n]的距离可以无限远,则输出-2,否则则输出牛[1]和牛[n]之间的最大距离。
差分约束入门题
首先记$d[i]$为第$i$头奶牛到第1头奶牛的距离,由于奶牛们按顺序排列,$d[i]<=d[i+1]+0$
第一种约束:$d[u]-d[v]<=w$,可作如下转化$d[u]<=d[v]+w$
观察发现这个式子很像求解最短路时spfa的松弛操作,的确与他有关,建立的模型便是$差分约束系统$。
第二种约束:$d[u]-d[v]>=w$,可转化为$d[v]<=d[u]-w$
根据红色标记的三种约束(如上)建图:
1.由i+1向i建立一条权值为0的边
记u=max(u,v),v=min(u,v),因为奶牛们是按顺序排列的,根据$d[i]$的意义,$d[u]>=d[v]$
2.由$u->v$连一条权值为w的边
3.由$u->v$连一条权值为-w的边
定理1:问题是否有解等价于图G是否没有负权回路。
证明:若G中无负权回路,我们可以求出v1其他顶点u的最短路长,设为d(u)。由于是最短路,因此对于任意边eE,e=uv,有d(u)+w(e)>=d(v),从而所有的约束条件都被满足,问题一定有解。若G中有负权回路,说明在任何时刻,G中至少有一个点v的最短路长可以更新,因此必须存在一条边e=uv,使得d(u)+w(e)<d(v)。所以无论何时,都会有某个约束条件不被满足,问题无解。(证毕)
定理2:若运行Bellman-Ford后,标号为N的顶点的最短路估计值仍为充分大,那么N和1的距离可以任意大。
证明:从刚才的操作可以看出,到了这一步,已经把含有负权回路的情况排除掉了。在图G中,该充分大的值比可能得到的最大距离大,因此,它和任意大的值对于G的效果都是一样的(同样大于合法的最大距离)。由于充分大的值在G中满足约束,所以任意大的值亦满足约束,从而距离可以任意大。(证毕)
定理3:若运行Bellman-Ford后,标号为N的顶点的最短路估计值比充分大小,那么它是N和1可能的最大距离。
证明:设D[i]是顶点i和1的最短路径估计值,d[i]是顶点i和1可能的最大距离。
我们首先证明,d[n]<=D[n],运用反证法。
假如d[n]>D[n],那么在Bellman-Ford运行之前,将赋予每个顶点i的充分大的值换成对应的d[i]。由于d本身满足所有约束条件,所以运行后,得出D'=d。由于充分大的值比所有d[i]都大,而求最短路运用的是逐步松弛操作,我们设立一个更大的初值不可能导致我们的终值反而更小。所以对于任意i,必定有D[i]>=D'[i],即有D[n]>=d[n],这与我们的假设矛盾。
然后我们证明,d[n]>=D[n]。
根据d[i]的定义,它是i和1的可能最大距离。由于D[i]是满足题目的所有约束的,所以D[i]是顶点i和1可能的距离。如果D[i]>d[i],那么与d[i]的定义矛盾。
综合上述,有D[i]=d[i]。从而D[n]是n和1可能的最大距离。(证毕)
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath> #define inf 0x7fffffff
#define N 100010
using namespace std; int n,ml,md,head[N],tot;
struct node{
int to,next,w;
}e[N]; void add(int u,int v,int w){
e[++tot].to=v,e[tot].next=head[u],head[u]=tot,e[tot].w=w;
} int d[N],in[N];
bool vis[N];
queue<int>Q;
int spfa(){
memset(vis,,sizeof(vis));
fill(d+,d++n,inf);
d[]=;Q.push();vis[]=;
while(!Q.empty()){
int u=Q.front();Q.pop();vis[u]=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!vis[v]){
vis[v]=;
in[v]++;
if(in[v]>n) return -;
Q.push(v);
}
}
}
}
if(d[n]==inf) return-;
else return d[n];
} int main()
{
scanf("%d%d%d",&n,&ml,&md);
for(int u,v,w,i=;i<=ml;i++){
scanf("%d%d%d",&u,&v,&w);
if(v>u) swap(v,u);
add(v,u,w);
}
for(int u,v,w,i=;i<=md;i++){
scanf("%d%d%d",&u,&v,&w);
if(u<v) swap(u,v);
add(u,v,-w);
}
for(int i=;i<n;i++) add(i+,i,);
printf("%d",spfa());
return ;
}
借鉴博客yew1eb AndyZhang Dust_Heart HopeForBetter
有关fill函数的用法
最新文章
- springmvc 表单提交
- 使用Python统计深圳市公租房申请人省份年龄统计
- SQL语句中,Conversion failed when converting datetime from character string.错误的解决办法
- MySQL数据库自带备份与恢复工具:MySQLdump.exe与mysql.exe
- Linux上free命令的输出
- 浅谈C中的malloc和free
- 批量修改Sqlserver中数据库对象的所属架构
- Socket异步通信学习一
- WebView 和Animation冲突
- C盘不能新建文件的问题解决办法
- CSS中float属性和clear属性的一些笔记
- cocos2d-x 发动机分析:程序如何开始和结束?
- LeetCode 162. Find Peak Element (找到峰值)
- [LeetCode] Maximum Vacation Days 最大化休假日
- 洛谷 P1045 &; [NOIP2003普及组] 麦森数
- mapper加载的3种方法
- 工作笔记:/bin/bash^M: 坏的解释器: 没有那个文件或目录 问题解决
- 修改linux的时间可以使用date指令
- luanet分布式lua框架
- 使用Xcode、Android Studio将项目链接到Git