题解 P1073 【最优贸易】

· · 题解

介绍一种暴力地不能再暴力的算法

分层图大法好！！！

分层图，就是在图上有一些不可逆操作，或循环操作时，把一个点拆成多个点，以表示不同状态的方法。（自己yy的定义，dalao勿喷）

举个栗子，在一张有图上跑最短路，可逆逆行一次。

或者没走一条路，所有路的权值就变成相反数

对于这题，有三个状态

（1） 还没买水晶球

（2） 买了但是没有卖

（3） 已经卖了

那么有些人可能会说第三个状态不必要，但是有个条件，那就是必须在n号点结束。所以不一定卖掉了就万事大吉，有可能为了卖高价跑到了一个到不了n的点，这种情况我们要舍弃。

我将一个点的三层分别设为x, x + n, x + 2 * n。我认为分层比较好理解

就是这样，跑一个SPFA就行啦。

具体的在代码里啦(代码写法可能比较奇怪，大概看看吧）

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int p[100005];
vector <pair <int, int> > V[300005];
bool inq[300005];
int d[300005];
queue <int> q;
int main(int argc, char **argv)
{
    int n, m, i;
    int x, y, z;
    int t;
    pair <int, int> r;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
      scanf("%d", &p[i]);
    for(i = 1; i <= m; i++)
    {
      scanf("%d%d%d", &x, &y, &z);
      V[x].push_back(make_pair(y, 0));//第一层间移动
      V[x].push_back(make_pair(y + n, -p[x]));//买了x的水晶球
      V[x + n].push_back(make_pair(y + n, 0));//第二层间移动
      V[x + n].push_back(make_pair(y + 2 * n, p[x]));//在x卖了水晶球
      V[x + 2 * n].push_back(make_pair(y + 2 * n, 0));//第三层间移动
      if(z == 2)//双向边
      {
        V[y].push_back(make_pair(x, 0));
        V[y].push_back(make_pair(x + n, -p[y]));
        V[y + n].push_back(make_pair(x + n, 0));
        V[y + n].push_back(make_pair(x + 2 * n, p[y]));
        V[y + 2 * n].push_back(make_pair(x + 2 * n, 0));
      }
    }
    for(i = 1; i <= 3 * n; i++)
      d[i] = -1e9;
    d[1] = 0;
    inq[1] = 1;
    q.push(1);
    while(q.size())
    {
      t = q.front();
      inq[t] = 0;
      q.pop();
      for(i = 0; i < V[t].size(); i++)
      {
        r = V[t][i];
        if(d[r.first] < d[t] + r.second)
        {
          d[r.first] = d[t] + r.second;
          if(!inq[r.first])
          {
            inq[r.first] = 1;
            q.push(r.first);
          }
        }
      }
    }
    cout << max(d[3 * n], 0) << endl;
    return 0;
}

最后说一句，在极限情况下，这张图有可能是300000个点，5000000条边的，正常最短路是不可能跑过去的。但是SPFA的特点就是，效率与图的形式有很大的关系，这个图大多数边都是0，并且比较有规律，所以能过。（还是感觉数据比较水）

这个最大一点200多ms，共900多ms。