POJ 3169 Layout （图论-差分约束）

Description

Input

Output

Sample Input

4 2 1
1 3 10
2 4 20
2 3 3

Sample Output

27

Hint

Source

题目大意：

n头奶牛按1到n排好序，md个限制及mt个限制,md行表示奶牛A与奶牛B相差最多D，mt个限制奶牛A与奶牛B相差最少D，问你奶牛1与奶牛n最多相差多少？

解题思路：

限制条件 ： 

1、相邻奶牛之间，编号大的距离大于编号小的，即 dist[1]-dist[2]<=0，dist[2]-dist[3]<=0，dist[3]-dist[4]<=0。。。。dist[n-1]-dist[n]<=0

2、md个限制 A与奶牛B相差最多D，dist[B]-dist[A]<=D

3、mt个限制奶牛A与奶牛B相差最少D，dist[B]-dist[A]>=D ，即 dist[B]-dist[A]<=D

v-u<=c，即添加 u->v=c 的单向边

有了这些元素，就可以用差分约束来解了，哈哈，是不是很简单！

差分约束学习可以参考：http://www.cnblogs.com/void/archive/2011/08/26/2153928.html

解题代码：

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

const int maxn=1100;
const int maxm=41000;
const int inf=0x3f3f3f3f;

struct edge{
    int u,v,w,next;
}e[maxm];

int head[maxn],dist[maxn],cnt;
int n;

void initial(){
    cnt=0;
    for(int i=0;i<=n;i++) head[i]=-1;
}

void adde(int u,int v,int w){
    e[cnt].u=u,e[cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt++;
}

void input(){
    int m,t;
    scanf("%d%d",&m,&t);
    while(m-- >0){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
    }
    while(t-- >0){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adde(v,u,-w);
    }
    for(int i=1;i<=n;i++){
        if(i>=2) adde(i,i-1,0);
        adde(0,i,0);
    }
}

bool spfa(int from){
    int s=from,num[maxn];
    bool visited[maxn];
    for(int i=0;i<=n;i++){
        num[i]=0;
        dist[i]=inf;
        visited[i]=false;
    }
    queue <int> q;
    q.push(s);
    visited[s]=true;
    dist[s]=0;
    while(!q.empty()){
        s=q.front();
        q.pop();
        for(int i=head[s];i!=-1;i=e[i].next){
            int d=e[i].v;
            if(dist[d]>dist[s]+e[i].w){
                dist[d]=dist[s]+e[i].w;
                if(!visited[d]){
                    visited[d]=true;
                    q.push(d);
                    num[d]++;
                    if(num[d]>n) return false;
                }
            }
        }
        visited[s]=false;
    }
    return true;
}

void solve(){
    if(spfa(0)){
        if(spfa(1)){
            if(dist[n]==inf) printf("-2\n");
            else printf("%d\n",dist[n]);
        }
    }else printf("-1\n");
}

int main(){
    while(scanf("%d",&n)!=EOF){
        initial();
        input();
        solve();
    }
    return 0;
}

POJ 3169 Layout （图论-差分约束）,布布扣,bubuko.com

POJ 3169 Layout （图论-差分约束）

原文：http://blog.csdn.net/a1061747415/article/details/31794623