POJ 3169 Layout（差分约束+最短路）题解

题意：有一串数字1~n，按顺序排序，给两种要求，一是给定u,v保证pos[v] - pos[u] <= w；二是给定u,v保证pos[v] - pos[u] >= w。求pos[n] - pos[1]最大，若无解输出-1，无穷多解输出-2。

思路：光看题目好像和最短路无关，其实这里用到了spfa的松弛操作来保证所给出的两种要求。若pos[v] - pos[u] >= w，则pos[v] +(- w) >= pos[u]，也就是pos[v] +(- w) < pos[u]时进行松弛，建一条边v->u，权值-w，这就和spfa中的那一步对应上了，于是转化为了最短路。另一种条件也是如此操作。无解的情况应为出现了负环；无穷多解的情况为1和n没有条件约束，也就是1没有路通向n。

参考：

夜深人静写算法（四） - 差分约束

代码：

#include<cstdio>

#include<set>

#include<cmath>

#include<stack>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = +;

const int INF = 0x3f3f3f3f;

struct Edge{

    int v,cost;

    Edge(int _v = ,int _cost = ):v(_v),cost(_cost){}

};

vector<Edge> G[maxn];

bool vis[maxn];

int cnt[maxn];

int dist[maxn];

void addEdge(int u,int v,int cost){

    G[u].push_back(Edge(v,cost));

}

bool spfa(int st,int n){

    memset(vis,false,sizeof(vis));

    memset(dist,INF,sizeof(dist));

    vis[st] = true;

    dist[st] = ;

    queue<int> q;

    while(!q.empty()) q.pop();

    q.push(st);

    memset(cnt,,sizeof(cnt));

    cnt[st] = ;

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = ;i < G[u].size();i++){

            int v = G[u][i].v;

            if(dist[v] > dist[u] + G[u][i].cost){

                dist[v] = dist[u] + G[u][i].cost;

                if(!vis[v]){

                    vis[v] = true;

                    q.push(v);

                    if(++cnt[v] > n) return false;

                }

            }

        }

    }

    return true;

}

int main(){

    int n,ml,md;

    scanf("%d%d%d",&n,&ml,&md);

    for(int i = ;i <= n;i++) G[i].clear();

    for(int i = ;i <= ml;i++){ //at most -> v - u <= w ->  v <= w + u

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addEdge(u,v,w);

    }

    for(int i = ;i <= md;i++){ //at least -> v - u >= w -> u <= -w + v

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addEdge(v,u,-w);

    }

    bool cannot = spfa(,n);

    if(!cannot){

        printf("-1\n");

    }

    else{

        if(dist[n] == INF){

            printf("-2\n");

        }

        else{

            printf("%d\n",dist[n]);

        }

    }

    return ;

}

巴特西

POJ 3169 Layout（差分约束+最短路）题解

最新文章

热门文章