洛谷 P4878 [USACO05DEC] 布局

Description

• 正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。FJ 有编号为 1…N的 N 头奶牛 (2≤N≤1000)。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

  有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数

  给出 ML对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 MD 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 (1≤ML, MD≤10的4次方)

  请计算：如果满足上述所有条件，1 号奶牛和 N 号奶牛之间的距离最大为多少。

Input

• 第一行：三个整数 N,ML,MD，用空格分隔。

  第 2…ML+1 行：每行三个整数 A,B,D，用空格分隔，表示 A号奶牛与 B 号奶牛之间的距离须 ≤D。保证 1≤A<B≤N,1≤D≤10的6次方

  第 ML+2…ML+MD+1行：每行三个整数 A,B,D，用空格分隔，表示 A 号奶牛与 B 号奶牛之间的距离须 ≥D。保证 1≤A<B≤N, 1≤D≤10的6次方

Output

• 一行，一个整数。如果没有合法方案，输出 -1. 如果有合法方案，但 1 号奶牛可以与 N 号奶牛相距无穷远，输出 -2. 否则，输出 111 号奶牛与 NNN 号奶牛间的最大距离。

Sample Input

4 2 1

1 3 10

2 4 20

2 3 3

Sample Output

27

题解：

• 差分约束。
• 这题又让我对差分约束有了一个新的理解。
• 如题，题中有两个问题。1：是否有解。 2：是否无穷远，不是，输出最大距离
• 对于第1个问题实则就是问你图中是否有环。第2个问题实则是问你图是否连通，不连通当然是无穷远（无穷多个解），连通了才可以输出最大距离。
• 反思之前做过的差分约束。唯独这题是具体到了两元素之间的关系。这个时候，就不能建超级源了。因为假如你加了超级源后不连通的图变成了连通的图。这样两元素的关系不在是最原本的状态了。
• 所以，再一次总结差分约束：
  1. 观察设问是求最大值还是最小值？
     • 最大值：统一将不等式化成x <= y + c的形式。建图：add(y, c, x)。跑最短路。
     • 最小值：统一将不等式化成x >= y + c的形式。建图：add(y, c, x)。跑最长路。
  2. 观察题面是求什么类型的问题？
     • 可行性：建立超级源，判环。
     • 广义的答案：建立超级源，跑spfa
     • 狭义的答案（具体到了两元素）：不能建立超级源，从其中一个点跑spfa

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 200005using namespace std;struct E {int next, to, dis;} e[N];int n, m1, m2, num;int h[N], dis[N], cnt[N];bool vis[N];int read(){    int x = 0; char c = getchar();    while(c < '0' || c > '9') c = getchar();    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}    return x;}void add(int u, int v, int w){    e[++num].next = h[u];    e[num].to = v;    e[num].dis = w;    h[u] = num;}int spfa(int s){    queue
        
          que;    memset(dis, 0x3f, sizeof(dis));    memset(vis, 0, sizeof(vis));    dis[s] = 0, vis[s] = 1, que.push(s);    while(!que.empty())    {        int now = que.front();        cnt[now]++;        if(cnt[now] >= n) return -1;        que.pop();  vis[now] = 0;        for(int i = h[now]; i != 0; i = e[i].next)            if(dis[now] + e[i].dis < dis[e[i].to])            {                dis[e[i].to] = dis[now] + e[i].dis;                if(!vis[e[i].to])                    vis[e[i].to] = 1, que.push(e[i].to);            }    }    if(dis[n] - dis[1] == 0x3f3f3f3f) return -2;    else return dis[n] - dis[1];}int main(){    cin >> n >> m1 >> m2;    for(int i = 1; i <= m1; i++)    {        int a = read(), b = read(), c = read();        add(a, b, c);    }    for(int i = 1; i <= m2; i++)    {        int a = read(), b = read(), c = read();        add(b, a, -c);    }    for(int i = 1; i <= n; i++) add(n + 1, i, 0);    if(spfa(n + 1) == -1) {cout << -1; return 0;}    else cout << spfa(1);    return 0;}