Layout G

题目传送门qwq

前言

不得不说，这道题读下来完全就是 模板题！（当然除最后三个万恶的\(hack\)数据以外）

如果有不了解的差分约束系统的，珂以看这篇博客啊

分析

• \(N\)个点，给出\(M_L\)组\(≤\)的关系，\(M_D\)组\(≥\)的关系

这....不就是约束条件嘛！那最直观的解决方法不就是差分约束系统嘛！

• 对于差分约束系统的题，我们还是要先判断是跑最短路还是最长路

继续看题，发现要求出从\(1\)到\(N\)的最大距离

我们知道，求最大解就是跑最短路，求最小解就是跑最长路（不知道的还是上面那篇博客qwq）

初步思路已经出来了：跑最短路的差分约束系统模板

• 我们再来看看输出格式：

1. 如果从\(1\)到\(N\)没有合法方案，则输出“\(-1\)”

2. 如果从\(1\)到\(N\)的距离为无限大，则输出“\(-2\)”

3. 否则输出从\(1\)到\(N\)的最大距离

如果不好理解，可以转换成如下：

1. 如果从\(1\)到\(N\)存在环，则是“\(-1\)”

2. 如果\(1\)无法到达\(N\)，则是“\(-2\)”

3. 否则输出从\(1\)到\(N\)的最大距离

• 好了，来看看上面思路编出来的代码（别急着说为什么A不了，因为还有\(hack\)在）

PS：这里和下面的代码皆使用 \(deque\)（双端队列），这是 \(SPFA\)的一种叫做\(SLF\)的优化

#include <bits/stdc++.h>
using namespace std;
deque<int> q;
int n,ml,md,u,v,w,flag;
int tot,dis[520010],vis[520010],cnt[520010],head[520010];

struct node {
    int to,net,val;
} e[520010];

inline void add(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].net=head[u];
    head[u]=tot;
}

inline void spfa() {
    for(register int i=1;i<=n;i++) {
        vis[i]=0;
        dis[i]=2005020600;
    }
    dis[1]=0;
    vis[1]=1;
    cnt[1]=1;
    q.push_back(1);
    while(!q.empty()) {
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(register int i=head[x];i;i=e[i].net) {
            int v=e[i].to;
            if(dis[v]>dis[x]+e[i].val) {
                dis[v]=dis[x]+e[i].val;
                if(cnt[v]==n) {
                    flag=1;
                    return ;
                }
                if(!vis[v]) {
                    vis[v]=1;
                    cnt[v]++;
                    if(!q.empty()&&dis[q.front()]<dis[v]) q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d",&n,&ml,&md);
    for(register int i=1;i<=ml;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(register int i=1;i<=md;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,-w);
    }
    spfa();
    if(flag==1) puts("-1");
    else {
        if(dis[n]==2005020600) puts("-2");
        else printf("%d",dis[n]);
    }
    return 0;
}

优化

我们发现，最后三组\(hack\)数据过不了（可恶啊）

• 为什么？

因为题目给出的数据并不保证图的连通性！

• 什么意思？

\(1\)有可能是“孤儿点”啊！那图就不连通了，结果就是上面的程序WA掉了

• 怎么优化？

我们就先特别跑一遍，判断图是否连通，如果连通就继续进行上面的操作；如果不连通就直接输出“\(-1\)”即可

• 特别处理

这里我们引入“超级源点”来帮助我们判断图的连通性

即：建立一个点\(0\)，然后与\(1\)到\(N\)的每个点都连一条边权为\(0\)的边，这样我们就可以通过跑一遍额外的\(SPFA\)来判断图的连通性了（这也算作差分约束系统的一种基础操作吧）

• 最后给出\(100pts\)的\(Code\)

#include <bits/stdc++.h>
using namespace std;
deque<int> q;
int n,ml,md,u,v,w,flag;
int tot,dis[520010],vis[520010],cnt[520010],head[520010];

struct node {
    int to,net,val;
} e[520010];

inline void add(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].net=head[u];
    head[u]=tot;
}

inline void spfa(int s) {
    for(register int i=1;i<=n;i++) {
        vis[i]=0;
        dis[i]=2005020600;
    }
    dis[s]=0;
    vis[s]=1;
    cnt[s]=1;
    q.push_back(s);
    while(!q.empty()) {
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        for(register int i=head[x];i;i=e[i].net) {
            int v=e[i].to;
            if(dis[v]>dis[x]+e[i].val) {
                dis[v]=dis[x]+e[i].val;
                if(cnt[v]==n) {
                    flag=1;
                    return ;
                }
                if(!vis[v]) {
                    vis[v]=1;
                    cnt[v]++;
                    if(!q.empty()&&dis[q.front()]<dis[v]) q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d",&n,&ml,&md);
    for(register int i=1;i<=n;i++) add(0,i,0);
    for(register int i=1;i<=ml;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(register int i=1;i<=md;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,-w);
    }
    spfa(0);
    if(flag==1) {
        puts("-1");
        return 0;
    }
    spfa(1);
    if(flag==1) puts("-1");
    else {
        if(dis[n]==2005020600) puts("-2");
        else printf("%d",dis[n]);
    }
    return 0;
}

最后，如果这篇题解有任何错误或您有任何不懂的，欢迎留言区评论啊，我会及时改正和回复，谢谢各位dalao啊qwq