poj 3169 Layout(线性差分约束,spfa:跑最短路+判断负环)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 15349 | Accepted: 7379 |
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,m1,m2
n头牛,每头牛跟其他的牛直接的距离有一定的约束
m1个约束1,m2个约束2
约束1:
a b c 表示a牛和b牛之间的距离最多c
约束2:
a b c 表示a牛和b牛之间的距离最少c
问你两头牛之间的最大距离至少是多少才能满足所有的约束
x[i]表示牛i的在x[i]处或者说牛i在距离原点x[i]的地方
x[a]-x[b]<=c
约束2可以表示为:
x[b]-x[a]<=-c
按照j到i建图,权值为c
然后起点是1,跑个最短路(不能使用dj,因为存在负权)
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<set>
#include<map>
#include<list>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 9999999999
#define me(a,x) memset(a,x,sizeof(a))
int mon1[]= {,,,,,,,,,,,,};
int mon2[]= {,,,,,,,,,,,,};
int dir[][]= {{,},{,-},{,},{-,}}; int getval()
{
int ret();
char c;
while((c=getchar())==' '||c=='\n'||c=='\r');
ret=c-'';
while((c=getchar())!=' '&&c!='\n'&&c!='\r')
ret=ret*+c-'';
return ret;
}
void out(int a)
{
if(a>)
out(a/);
putchar(a%+'');
} #define max_v 1005
struct node
{
int v;
LL w;
node(int vv=,LL ww=):v(vv),w(ww){}
};
LL dis[max_v];
int vis[max_v];
int cnt[max_v];
vector<node> G[max_v];
queue<int> q; void init()
{
for(int i=;i<max_v;i++)
{
G[i].clear();
dis[i]=INF;
vis[i]=;
cnt[i]=;
}
while(!q.empty())
q.pop();
} int spfa(int s,int n)
{
vis[s]=;
dis[s]=;
q.push(s);
cnt[s]++; while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=; for(int j=;j<G[u].size();j++)
{
int v=G[u][j].v;
LL w=G[u][j].w; if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(vis[v]==)
{
q.push(v);
cnt[v]++;
vis[v]=; if(cnt[v]>n)
return ;
}
}
}
}
return ;
}
int f(int u,int v)
{
for(int j=;j<G[u].size();j++)
{
if(G[u][j].v==v)
return ;
}
return ;
}
int main()
{
int n,a,b;
while(~scanf("%d %d %d",&n,&a,&b))
{
init();
int x,y,w;
while(a--)
{
scanf("%d %d %d",&x,&y,&w);
if(f(x,y))
G[x].push_back(node(y,w));
}
while(b--)
{
scanf("%d %d %d",&x,&y,&w);
if(f(y,x))
G[y].push_back(node(x,-w));
}
int flag=spfa(,n);
if(flag==)
{
printf("-1\n");
}else if(dis[n]<INF)
{
printf("%lld\n",dis[n]);
}else
{
printf("-2\n");
}
}
return ;
}
/*
题目意思:
给n,m1,m2
n头牛,每头牛跟其他的牛直接的距离有一定的约束
m1个约束1,m2个约束2
约束1:
a b c 表示a牛和b牛之间的距离最多c
约束2:
a b c 表示a牛和b牛之间的距离最少c
问你两头牛之间的最大距离至少是多少才能满足所有的约束 分析:
x[i]表示牛i的在x[i]处或者说牛i在距离原点x[i]的地方 约束1可以表示为:
x[a]-x[b]<=c
约束2可以表示为:
x[b]-x[a]<=-c <=代表的是最大值,代表的是最短路,表达式形式为x[i]-x[j]<=c
按照j到i建图,权值为c
然后起点是1,跑个最短路(不能使用dj,因为存在负权)
1到n的最短路就是能满足所有牛约束的最小距离值 */
最新文章
- java之AbstractStringBuilder类详解
- BZOJ4033 [HAOI2015]T1
- [C]判断一个文件是否是jpg格式
- MVVM知识库总结
- Ubuntu设置中文
- javascript调用外部wpf的方法
- BZOJ 1684: [Usaco2005 Oct]Close Encounter
- Floodlight controller 线程池模型
- JAVA 验证码生成(转)
- JS实现60s倒计时(亲测有效),及span标签如何使用和禁用onclick事件
- Struts2------Result处理&;获取页面请求参数&;API
- ssm日期格式转换
- JMeter 接口测试-if控制器
- electron-vue:Vue.js 开发 Electron 桌面应用
- C++ 是 编程界 的 背锅侠
- linux 系统命令和方法
- CRM项目再分析建表
- mysql创建表的注意事项
- windows宿主机ping不通Docker容器的解决办法
- Apache Flume 安装文档、日志收集