Solution [USACO05DEC]layout布局
题目大意:给定一系列形如(a_{j} - a_{i} leq d ; | ; i < j)或(a_{j} - a_{i} geq d ; | ; i < j)的约束条件,求(a_{n} - a_{1})的最大值
差分约束
分析:看到那个标志性的(a_{j} - a_{i} leq d ; | ; i < j),应该第一反应就是差分约束吧?
至于那个(a_{j} - a_{i} geq d ; | ; i < j),我们直接乘一个(-1)它就服服帖帖的变成(a_{i} - a_{j} leq -d)了
然后我们就把约束条件统一成了(a - b leq d)的形式了
再来看题,要求的是(a_{n} - a_{1})的最大值对吧?
回想一下差分约束算法是怎么和最短路扯上联系的:
$ecause a_{j} - a_{i} leq d $
( herefore a_{j} leq a_{i} + d)
那么我们发现,只要(a_i)的值确定了,(a_j)的最值我们就确定了,即(a_{i}) "约束" 了 (a_{j})
然鹅你要求的是(a_{n} - a_{1})的最大值对吧?那不就是在一系列的约束条件下都尽量走边权最大的边吗?
那么如果两个点(u,v)之间有多条连边呢?我们是不是只能走边权最小的边?这是由于题目中约束条件是(a_{j} - a_{i} leq d)而导致的(另一个条件通过乘(-1)的形式来变形).
走边权最小的边,然后求边权之和.这不就是最短路吗?只不过要注意几个细节罢了
- 有负边权 这个好办,直接(SPFA)
虽然他死了 - 判断是否有解 这个直接(SPFA)顺带判负环即可
- 判断(a_n)否可以为无穷大 这个只要以(1)为出发点跑一次最短路,然后看看终点值是否为(INF)即可.如果终点值为(INF),说明约束条件约束不了终点的取值
- 可能炸(int)
即使没有那几组毒瘤的(hack)数据,我们还是应该想到图可能不连通.解决方法也很简单:
- 利用题目中所给的性质,即奶牛们是按照编号排序的 直接在(a_{i}) 和 (a_{i + 1})之间连一条权值为(0)的边即可
- 以(0)为顶点,向每个点连一条权值为(0)的虚拟边 然后以(0)为起点跑(SPFA)判断图是否连通,之后以(1)为顶点跑(SPFA)求解
附上我丑陋的代码:
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;
const int maxn = 1024;
const int maxm = 1e5;
typedef long long ll;//好像有可能炸int
struct Edge{//存边
int from,to,dist;
Edge() = default;
Edge(int a,int b,int c):from(a),to(b),dist(c){}
}Edges[maxm];
int head[maxn],nxt[maxm],n;
inline void addedge(int from,int to,int dist){
static int tot;
Edges[++tot] = Edge(from,to,dist);
nxt[tot] = head[from];
head[from] = tot;
}//朴素的前向星存图
ll dist[maxn];
int cnt[maxn],inq[maxn];
inline void spfa(int s){//更加朴素的SPFA,原来我用了STL,懒得手打了(逃。。。)
queue<int> Q;
memset(dist,0x3f,sizeof(dist));
dist[s] = 0;
Q.push(s),inq[s] = 1;
while(!Q.empty()){
int u = Q.front();Q.pop();
inq[u] = 0;
for(int i = head[u];i;i = nxt[i]){
Edge &e = Edges[i];
if(dist[e.from] + e.dist < dist[e.to]){
dist[e.to] = dist[e.from] + e.dist;
if(!inq[e.to]){
Q.push(e.to),inq[e.to] = 1;
if(++cnt[e.to] > n){//判负环
printf("-1
");
exit(0);
}
}
}
}
}
}
int ml,md;
int main(){
#ifdef LOCAL
freopen("fafa.in","r",stdin);
#endif
scanf("%d %d %d",&n,&ml,&md);
for(int u,v,d,i = 1;i <= ml;i++)
scanf("%d %d %d",&u,&v,&d),addedge(u,v,d);
for(int u,v,d,i = 1;i <= md;i++)
scanf("%d %d %d",&u,&v,&d),addedge(v,u,-d);//按照题中所给的要求连边
for(int i = 1;i <= n;i++)//连虚拟边
addedge(0,i,0);
spfa(0),spfa(1);//先以0为顶点跑SPFA判负环,然后以1为顶点跑SPFA求解
if(dist[n] == 0x3f3f3f3f3f3f3f3f)printf("-2
");//如果约束不到点n,那么点n的值就可以为无穷大
else printf("%lld
",dist[n]);
return 0;//圆满收工
}