题解 P1073 【最优贸易】

· · 题解

** 好不容易有道自己独立写出来的题

这题我一开始没注意到要到n。

开始要从n点反向BFS一次标记可以选择的点

然后用类似DP的方法 dp[i][0]表示从起点到这里的最小买入价

dp[i][1]表示从起点到这里的最大利润

转移方程：（假设当前点为u，出边的点为v）

dp[v][0]=min( dp[v][0] , min( dp[u][0] , w[u] ) )要么是之前点的价格，要么是当前点的价格

dp[v][1]=max( dp[v][1] , w[u]-dp[u][0] ) 在u点卖出

第一次对求出dp数组的做法是DFS

TLE 3个点 RE 4个

想了一下，觉得爆栈的可能比较大，毕竟有环，而且刚开始的DFS里面遍历某一个点遍历到第三次（因为有可能会回来卖出，样例就是这样）才return

。。怎么破啊，只有用queue了呗

我又想了一下，DFS中我是用u来更新它的出边点v的dp值

只有dp值更优的时候，以v为起始点继续DFS才有意义，而原来的DFS太笨，无论怎样都继续DFS

。。判断。。判断。。判断更优才加入节点。。。队列。。

假如这个节点已经在队列里面了呢？额，那就来个inq数组防止重复

我灵光一闪，inq！！！！！！！

原来这个就像SPFA一样！！！！

顺着SPFA的思路写下去，居然A了= =

**


#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
const int maxm=2*(500000+10);
const int INF=(1<<30);
struct Edge{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
}e[maxm*2];

int first[maxn],next[maxm*2],w[maxn],dp[maxn][2],_first[maxn],n,m;
int ecnt=0;
int read()
{
    int ret=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar())ret=ret*10+ch-'0';
    return ret;
}

void add_edge(int u,int v)
{
    next[ecnt]=first[u];first[u]=ecnt;e[ecnt++]=Edge(u,v);
    next[ecnt]=_first[v];_first[v]=ecnt;e[ecnt++]=Edge(v,u);//这里的 _first存的是反向边，所以e数组和next数组要开两倍大小，用来支持第一次BFS
}

int can[maxn];
void init_data()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        w[i]=read();can[i]=-1;
        first[i]=_first[i]=-1;
        dp[i][0]=INF;dp[i][1]=-INF;
    }
    for(int i=1,u,v,ins;i<=m;i++)
    {
        u=read();v=read();ins=read();
        add_edge(u,v);
        if(ins==2) add_edge(v,u);
    }
}

int cnt[maxn],inq[maxn];
void bfs()
{
    queue<int>q;
    q.push(1);
    inq[1]=1;

    while(!q.empty())
    {
        int x=q.front();q.pop();
        inq[x]=0;
        if(can[x]==-1) continue;

        for(int i=first[x];i!=-1;i=next[i])
        {
            if(can[e[i].v]==-1) continue;
            int &d0=dp[e[i].v][0];
            int &d1=dp[e[i].v][1];
            if((d0>w[x] || d0>dp[x][0]) || (d1<w[x]-dp[x][0]))
            {
                d0=min(d0,min(w[x],dp[x][0]));
                d1=max(d1,w[x]-dp[x][0]);
                if(!inq[e[i].v]) q.push(e[i].v);
            }
        }
    }
    return ;
}

int vis[maxn];
void BFS()
{
    queue<int>q;
    q.push(n);

    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(can[x]!=-1) continue;
        can[x]=1;
        for(int i=_first[x];i!=-1;i=next[i])
            q.push(e[i].v);
    }
}

int main()
{
    init_data();
    BFS();             //标记可选择的点
    bfs();              //求DP数组
    int ans=-INF;
    for(int i=1;i<=n;i++)
      if(can[i]!=-1)
        ans=max(ans,dp[i][1]);
    if(ans<0) printf("0");
    else cout<<ans;
    return 0;
}