Layout

题目链接：

Rhttp://acm.hust.edu.cn/vjudge/contest/122685#problem/S

Description

```
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

</big>

##Input

<big>

Line 1: Three space-separated integers: N, ML, and MD.

Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

</big>

##Output

<big>

Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

</big>

##Sample Input

<big>

4 2 1

1 3 10

2 4 20

2 3 3

</big>

##Sample Output

<big>

27

</big>

##Hint

<big>

</big>

<br/>

##题意：

<big>

以两种形式给出若干组大小关系：

A和B的权值差最多是D.

A和B的权值差最少是D.

求#1和#N之间的最大权值差.

</big>

<br/>

##题解：

<big>

差分约束系统. 还需强化练习. 挖坑待填.

</big>

<br/>

##代码：

``` cpp

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <vector>

#define LL long long

#define eps 1e-8

#define maxn 31000

#define mod 1000000007

#define inf 0x3f3f3f3f

#define IN freopen("in.txt","r",stdin);

using namespace std;

int n,m1,m2;

int u[maxn],v[maxn],w[maxn];

int first[maxn], _next[maxn], edges;

int dis[maxn];

void add_edge(int s, int t, int ww) {

    u[edges] = s; v[edges] = t; w[edges] = ww;

    _next[edges] = first[s];

    first[s] = edges++;

}

int bell_man(int s, int t) {

    for(int i=1; i<=n; i++) dis[i]=inf; dis[s] = 0;

    for(int i=1; i<=n; i++) {

        for(int e=0; e<edges; e++) if(dis[v[e]] > dis[u[e]]+w[e]){

            dis[v[e]] = dis[u[e]]+w[e];

            if(i == n) return -1;

        }

     }

     if(dis[t] == inf) return -2;

     return dis[t];

}

int main(void)

{

    //IN;

    while(scanf("%d %d %d", &n, &m1, &m2) != EOF)

    {

        memset(first, -1, sizeof(first)); edges = 0;

        while(m1--) {

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

            add_edge(u, v, w);

        }

        while(m2--) {

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

            add_edge(v, u, -w);

        }

        for(int i=1; i<n; i++)

            add_edge(i+1, i, 0);

        int ans = bell_man(1, n);

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

POJ 3169 Layout （差分约束系统）

Layout

题目链接：

Description

最新文章

热门文章