sgu 298 差分限制（特定解）

題目：http://acm.sgu.ru/problem.php?contest=0&problem=298

題意：

給定n個點m條限制。

下面輸出 u v x 表示：

dis[u] - dis[v] >= x

然後建圖就是 u->v 邊權為-x

輸出一個解滿足 -10000<= dis[i] <= 10000。

若有多解輸出一個 dis[n] - dis[1] 最小的解。

分析：

最短路得到最大解，最長路得到最小解，然後判斷是否最大解全部不小于最小解。

因為要求dis[n]-dis[1]最小，那就令dis[n]為其最小解，dis[1]為其最大解，再spfa一遍就好。

有一個連等式：(規定求最短路的那個圖為正向邊和正權)正向邊正權最短路的解的結構=反向邊反權最長路解的結構=正向邊反權最長路解的值取相反數之後的結構=反向邊正權最短路解的值取相反數之後的結構。

代碼：

const int N =  + ;
struct Edge {
    int v, w, next;
};
Edge edge[N], fedge[N];
int head[N], fhead[N], d[N], fd[N], vis[N], num[N], n, cnt;
void addedge (int u, int  v, int w) {
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
    fedge[cnt].v = u;
    fedge[cnt].w = w;
    fedge[cnt].next = fhead[v];
    fhead[v] = cnt++;

}

bool spfa (int head[], Edge edge[], int d[]) {
    queue<int>q;
    for (int i = ; i <= n; i++) num[i] = , vis[i] = , q.push (i);
    while (!q.empty() ) {
        int u = q.front();
        q.pop();
        vis[u] = ;
        for (int i = head[u]; ~i; i = edge[i].next) {
            if (d[edge[i].v] > d[u] + edge[i].w) {
                d[edge[i].v] = d[u] + edge[i].w;
                if (!vis[edge[i].v]) {
                    q.push (edge[i].v);
                    vis[edge[i].v] = ;
                    if (++num[edge[i].v] > n) return ;
                }
            }
        }
    }
    return ;
}
int solve() {
    for (int i = ; i <= n; i++) d[i] = fd[i] = INF;
    if (!spfa (head, edge, d) ) return ;
    if (!spfa (fhead, fedge, fd) ) return ;
    for (int i = ; i <= n; i++)
        if (d[i] < -fd[i]) return ;
    d[n] = -fd[n];
    spfa (head, edge, d);
    for (int i = ; i < n; i++) printf ("%d ", d[i]);
    printf ("%d\n", d[n]);
    return ;
}
int main() {
    // freopen ("f.txt", "r", stdin);
    int u, v, w, m;
    while (~scanf ("%d%d", &n, &m) ) {
        memset (head, -, sizeof (head) );
        memset (fhead, -, sizeof (fhead) );
        cnt = ;

        for (int i = ; i < m; i++) {
            scanf ("%d%d%d", &u, &v, &w);
            addedge (u, v, -w);
        }

        if (!solve() ) puts ("-1");
    }
    return ;
}