(POJ) 1201 -- Intervals [差分約束系統]

http://poj.org/problem?id=1201

差分約束系統www。

考慮現在有很多不等式 x_i <= x_j + c ， 研究一下，會發現，這其實跟最短路徑的dis_i <= dis_j + w(i,j) 長得很像。

所以，遇到很多這種 x_i <= x_j + c的方程式，就可以使用最短路徑的建圖方法：連一條i到j的邊，邊權 = c。

那，這樣去跑最短路後，如果有遇到負環，那就代表無解。

那，如果有解的話，假設你是求從st開始求最短路徑到ed，那，dis_ed 就代表：在所有可行解中， x_ed - x_st 的最大值！

但是，這題要求的是最小的耶><。

可以先有一個小小的想法：我們可以去二分搜這個值，建一條x_st + min_dis <= x_ed 的邊。

會發現，如果是無解，那就是有負環！

那，在一點點觀察後，其實可以發現：要求x_ed - x_st  的最小值，其實就是 x_st - x_ed 的最大值，只是要取個負號XDD。

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;
const int N = 50006;
const int INF = (1<<27);

#define F first
#define S second

vector<pii> G[N];

void add_edge(int from,int to,int weight)
{
    G[from].push_back(make_pair(to,weight));
}

bool in_que[N];
int dis[N];

int spfa(int from,int to)
{
    queue<int> que;
    fill(dis,dis+N,INF);
    memset(in_que,0,sizeof(in_que));
    dis[from]=0;
    que.push(from);
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        in_que[t] = false;
        for (int i=0;G[t].size()>i;i++)
        {
            pii p=G[t][i];
            if (dis[p.F] > dis[t] + p.S)
            {
                dis[p.F] = dis[t] + p.S;
                if (!in_que[p.F])
                {
                    que.push(p.F);
                    in_que[p.F] = 1;
                }
            }
        }
    }
    return dis[to];
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        int nn=N-3;
        for (int i=0;nn>=i;i++)
        {
            G[i].clear();
        }
        int ed = 0;;
        int st = N-3;
        for (int i=1;n>=i;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            ++x;
            ++y;
            --x;
            add_edge(y,x,-z);
            ed = max(ed,y+1);
            st = min(st,x);
            //add_edge(x,y,z);
        }
        for (int i=st+1;ed>=i;i++)
        {
            add_edge(i,i-1,0);
            add_edge(i-1,i,1);
        }
        printf("%d\n",-spfa(ed,st));
    }
}