POJ-3169 Layout (差分约束+SPFA）

POJ-3169 Layout：http://poj.org/problem?id=3169

参考：https://blog.csdn.net/islittlehappy/article/details/81155802

题意：

　　一共有n头牛，有ml个关系好的牛的信息，有md个关系不好的牛的信息，对应输入的第一行的三个元素，接下来ml行，每行三个元素A,B,D，表示A牛和B牛相距不希望超过D，接下来md行，每行三个元素A,B,D表示A牛和B牛的相距至少要有D才行。求1号牛和n号牛的最大距离，如果距离无限大输出-2，如果无解输出-1。

思路：

　　设dis [ x ] 为x 到 0 位置的距离， v 的标号大于 u

　　我们要求 dis [ n ] - dis [ 1 ] <=x 即，x是n号牛与1号牛的最大距离

　　对于ml的关系好的牛有： dis [ v ] - dis [ u ] <= w; -------> dis [ v ] <= dis [ u ] + w; 建一条从u到v，权值为 w 边

　　对于md的关系差的牛有： dis [ v ] - dis [ u ] >= w; ---------> dis [ u ] <= dis [ v ] - w; 建一条从v到u，权值为 -w 边

　　则：我们的目标是 dis [ v ] <= dis [ u ] + x; 若碰到 dis [ v ] > dis [ u ] + x 边进行松弛

　　因此，应该跑最短路

虽然还不知道差分约束具体是什么，但是还是觉得这种解法好神奇。

/*

* @Author: chenkexing

* @Date:   2018-09-05 11:05:14

* @Last Modified by:   chenkexing

* @Last Modified time: 2018-09-06 13:38:17

*/

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

#define OKC ios::sync_with_stdio(false);cin.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

            const int maxn = 1e6+;

            vector<pii>mp[maxn];

            int in[maxn],cnt[maxn],dis[maxn],n;

            bool spfa(int s,int t){

                memset(in,,sizeof(in));

                memset(dis,inf,sizeof(dis));

                memset(cnt,,sizeof(cnt));

                queue<int>que;que.push(s);

                dis[s] = ;in[s] = ;cnt[s] ++;

                bool flag = false;

                while(!que.empty()){

                    int u = que.front();que.pop();

                    in[u] = ;

                    if(cnt[u] > n){

                        flag = true;

                        break;

                    }

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

                        int v = mp[u][i].fi;

                        if(dis[v] > dis[u] + mp[u][i].se ){

                            dis[v] = dis[u] + mp[u][i].se;

                            if(in[v] == ){

                                in[v] = ;

                                que.push(v);

                                cnt[v]++;

                            }

                        }

                    }

                }

                if(flag)return true;

                return false;

            }

int main(){

            int m1,m2;

            scanf("%d%d%d", &n, &m1, &m2);

            for(int i=; i<=m1; i++){

                int u,v,w;

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

                mp[u].pb(pii(v,w));

            }

            for(int i=; i<=m2; i++){

                int u,v,w;

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

                mp[v].pb(pii(u,-w));

            }

            if(spfa(,n) == false){

                if(dis[n] >= inf)printf("-2\n");

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

            }

            else printf("-1\n");

            return ;

}

POJ - 3169

巴特西

POJ-3169 Layout (差分约束+SPFA）

题意：

思路：

最新文章

热门文章