【解题报告】 POJ - 3159 Candies(差分约束、最短路)

原题地址

其实这个题目思考起来和实现起来并不难 ,但是为了码一下发现的dalao的博客,还是写一下题解

dalao博客:
夜深人静写算法(四) - 差分约束

真的写的非常好啊!可以说是帮我又把最短路和建图的知识复习了一遍,吹爆dalao,简单的逛了一下,他其他的文章包括dp、线段树、树状数组等等都写的非常认真非常仔细,还附题集,每一题还点出了重点是什么,可以说是非常良心了!决定了,以后就跟着这个dalao混了!

思路

首先,差分约束这个东西听起来很高深,但实际上逻辑非常友好,处理一组不等式,求最大最小值,最大值会被其他比较小的最大值约束,最小值会被其他比较大的最小值约束,最后统统可以转换为求最短路/最长路的问题,这就是差分约束的关键。本题中给了m条边,要求求第1个节点到第n个节点的最大值,这个最大值实际上是求n到1的最短路,也就是被约束住了,这么样去想,就很容易明白了。
当然,差分约束的应用并没有那么简单,想要用好还是要多多练习的。
顺便,这个题目听说想要不TLE,必须用堆优化的dijkstra,或者用栈优化的spfa,这就很玄学了,好像是说栈队列优化的spfa并没有相差很多,但是这个题目如果用队列就超时,很奇怪。
(另外:链式前向星很好的一点是不会爆内存,而且存权值很方便,如果用邻接表有时候很难存下一大组数据,写的时候也很没底的,这个一定要掌握。)

spfa + stack:

#include <iostream>
#include <stack>
#include <utility>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const static int maxn = 30010;
typedef pair<int, int> pii;
bool vis[maxn];
int d[maxn];
int n, m, len;
int head[maxn];
struct edge
{
    int v, w;
    int next;
}e[150010];
void add(int u, int v, int w)
{
    e[len].v = v;
    e[len].w = w;
    e[len].next = head[u];
    head[u] = len++;
}
void spfa(int x)
{
    stack <int> s;
    s.push(x);
    d[x] = 0;
    vis[x] = true;
    while(!s.empty())
    {
        int u = s.top();
        s.pop();
        vis[u] = false;
        for(int i=head[u]; i!=-1; i = e[i].next)
        {
            int v = e[i].v;
            if(d[v] > d[u] + e[i].w)
            {
                d[v] = d[u] + e[i].w;
                if(!vis[v])
                {
                    s.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        d[i] = inf;
        head[i] = -1;
        vis[i] = false;
    }
    for(int i=1; i<=m; i++)
    {
        int a, b, w;
        scanf("%d %d %d",&a, &b, &w);
        add(a, b, w);
    }
    spfa(1);
    printf("%d", d[n]);
    return 0;
}

dijkstra + priority_queue:

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const static int maxn = 30010;
typedef pair<int, int> pii;
bool vis[maxn];
int d[maxn];
int n, m, len;
int head[maxn];
struct edge
{
    int v, w;
    int next;
}e[150010];
void add(int u, int v, int w)
{
    e[len].v = v;
    e[len].w = w;
    e[len].next = head[u];
    head[u] = len++;
}
void dijstra(int x)
{
    priority_queue<pii, vector<pii>, greater<pii> > q;
    d[x] = 0;
    q.push(make_pair(d[x], x));
    while(!q.empty())
    {
        pii temp = q.top();
        q.pop();
        int u = temp.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i=head[u]; i!=-1; i = e[i].next)
        {
            int v = e[i].v;
            if(d[v] > d[u] + e[i].w && !vis[v])
            {
                d[v] = d[u] + e[i].w;
                q.push(make_pair(d[v], v));
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        d[i] = inf;
        head[i] = -1;
        vis[i] = false;
    }
    for(int i=1; i<=m; i++)
    {
        int a, b, w;
        scanf("%d %d %d",&a, &b, &w);
        add(a, b, w);
    }
    dijstra(1);
    printf("%d", d[n]);
    return 0;
}
上一篇:[LeetCode] 101. 对称二叉树


下一篇:POJ 3159 :Candies 【线性差分约束 链式前向星 栈优化SPFA】