NOIP2009T3最优贸易（Dfs + spfa）

洛谷传送门

看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以及各种奇奇怪怪的东西。说实话我连样例都没过，然后提交一下试试，得了10分。

然而我发现，要求赚最多钱，就是到那个点的路径上的最大价格 - 最小价格。

两边dfs——

最小价格可以从前往后搜来算。

最大价格可以从后往前搜来算。

最后枚举一边所有点maxx - minn的最大值就好。

说出来你可能不信，我是看的题解。

——代码

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

using namespace std;

int n, m, cnt1, cnt2, ans;

int a[], next1[], to1[], head1[], next2[], to2[],

    head2[], maxx[], minn[];

inline void add1(int x, int y)

{

    to1[cnt1] = y;

    next1[cnt1] = head1[x];

    head1[x] = cnt1++;

}

inline void add2(int x, int y)

{

    to2[cnt2] = y;

    next2[cnt2] = head2[x];

    head2[x] = cnt2++;

}

inline void dfs2(int u, int k)

{

    int i, v;

    maxx[u] = max(maxx[u], k);

    for(i = head2[u]; i != -; i = next2[i])

    {

        v = to2[i];

        if(maxx[v] < k) dfs2(v, max(k, a[v]));

    }

}

inline void dfs1(int u, int k)

{

    int i, v;

    minn[u] = min(minn[u], k);

    for(i = head1[u]; i != -; i = next1[i])

    {

        v = to1[i];

        if(minn[v] > k) dfs1(v, min(k, a[v]));

    }

}

int main()

{

    int i, j, x, y, z;

    memset(head1, -, sizeof(head1));

    memset(head2, -, sizeof(head2));

    scanf("%d %d", &n, &m);

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

    {

        scanf("%d", &a[i]);

        maxx[i] = -1e9;

        minn[i] = 1e9;

    }

    for(i = ; i <= m; i++)

    {

        scanf("%d %d %d", &x, &y, &z);

        if(z == )

        {

            add1(x, y);

            add1(y, x);

            add2(x, y);

            add2(y, x);

        }

        else

        {

            add1(x, y);

            add2(y, x);

        }

    }

    dfs1(, a[]);

    dfs2(n, a[n]);

    for(i = ; i <= n; i++) ans = max(ans, maxx[i] - minn[i]);

    printf("%d", ans);

    return ;

}

其中dfs不用设置vis来记录是否被访问过，因为有双向道路，所以走到一个点有可能会返回来，所以进行深搜的判断标准是目标点（姑且这么说吧）的最大最小值小于或大于当前点的最大最小值。这样即使走到后面的点，发现前面的点需要修改，也可以改回去。

也可以用 spfa ，改变一下松弛操作，dis 数组表示到当前点的路径上买入的最小值，最后统计一遍就行。

——代码

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int MAXN = ;

 int n, m, cnt, cnt1, ans;

 int a[MAXN], head[MAXN], to[MAXN], next[MAXN], head1[MAXN], to1[MAXN], next1[MAXN], dis[MAXN];

 bool b[MAXN], vis[MAXN];

 queue <int> q;

 inline void add(int x, int y)

 {

     to[cnt] = y;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline void add1(int x, int y)

 {

     to1[cnt1] = y;

     next1[cnt1] = head1[x];

     head1[x] = cnt1++;

 }

 inline void dfs(int u)

 {

     int i, v;

     b[u] = ;

     for(i = head1[u]; i != -; i = next1[i])

     {

         v = to1[i];

         if(!b[v]) dfs(v);

     }

 }

 inline void spfa(int u)

 {

     int i, v;

     memset(dis,  / , sizeof(dis));

     q.push(u);

     dis[u] = a[u];

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         vis[u] = ;

         for(i = head[u]; i != -; i = next[i])

         {

             v = to[i];

             if(dis[v] > min(dis[u], a[v]) && b[v])

             {

                 dis[v] = min(dis[u], a[v]);

                 if(!vis[v])

                 {

                     q.push(v);

                     vis[v] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     int i, j, x, y, z;

     scanf("%d %d", &n, &m);

     for(i = ; i <= n; i++) scanf("%d", &a[i]);

     memset(head, -, sizeof(head));

     memset(head1, -, sizeof(head1));

     for(i = ; i <= m; i++)

     {

         scanf("%d %d %d", &x, &y, &z);

         if(z == )

         {

             add(x, y);

             add1(y, x);

         }

         else

         {

             add(x, y);

             add(y, x);

             add1(x, y);

             add1(y, x);

         }

     }

     dfs(n);

     spfa();

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

         if(b[i])

             ans = max(ans, a[i] - dis[i]);

     printf("%d", ans);

     return ;

 }

巴特西

NOIP2009T3最优贸易（Dfs + spfa）

最新文章

热门文章