题解 P1073 【最优贸易】

compile_error · 2017-06-05 21:05:20 · 题解

• 题目上说要找一条路径上的差值最大，所以应该想到建两个图找最大值与最小值

• 所以就想到要找到每个节点的可到达的最大值与最小值

• 我这里用的是两个BFS，一个正向的BFS找最小值，一个反向的BFS找最大值

• BFS中每一次记录这个节点的下一个节点与这个一个节点的权值的最小值(最大值)

需要注意的是就算之前已经走过这个节点也需要再比较是否需要更新因为可能会有双向边

PS：蒟蒻的代码 写的很啰嗦

#include <bits/stdc++.h>

using namespace std;
const int maxn=100000+5;
const int maxm=500000+5;

struct e{
    int to;
    int next;
}edge1[maxm],edge2[maxm];
int head1[maxn],edge_len1=0; //正向图
int head2[maxn],edge_len2=0; //反向图
int w[maxn];
int n,m;
int minx[maxn],maxx[maxn]; //当前节点可以到达的最小值和最大值

void edge_add1(int u,int v) //正向建图
{
    edge1[++edge_len1].to=v;
    edge1[edge_len1].next=head1[u];
    head1[u]=edge_len1;
}
void edge_add2(int u,int v) //反向建图
{
    edge2[++edge_len2].to=v;
    edge2[edge_len2].next=head2[u];
    head2[u]=edge_len2;
}
int m_max(int a,int b,int c)
{
    if(a>b && a>c) return a;
    if(b>a && b>c) return b;
    return c;
}
int m_min(int a,int b,int c)
{
    if(a<b && a<c) return a;
    if(b<a && b<c) return b;
    return c;
}
bool visit[maxn];
void bfs1() //正向BFS找一条路径上的最小值
{
    memset(minx,0x7f7f,sizeof(minx));
    queue<int> q;
    q.push(1);
    minx[1]=w[1];
    while(!q.empty())
    {
        int node=q.front();q.pop();
        for(int i=head1[node];i;i=edge1[i].next)
        {
            int now=edge1[i].to;
            minx[now]=m_min(minx[node],w[now],minx[now]);
            if(!visit[now])
            {
                q.push(now);
                visit[now]=true;
            }
        }
    }
}
void bfs2() //反向BFS找一条路径的最大值
{
    memset(visit,false,sizeof(visit));
    queue<int> q;
    q.push(n);
    maxx[n]=w[n];
    while(!q.empty())
    {
        int node=q.front();q.pop();
        for(int i=head2[node];i;i=edge2[i].next)
        {
            int now=edge2[i].to;
            maxx[now]=m_max(maxx[node],maxx[now],w[now]);
            if(!visit[now])
            {
                q.push(now);
                visit[now]=true;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z==1)
        {
            edge_add1(x,y); //正反建图
            edge_add2(y,x);
        }
        if(z==2)
        {
            edge_add1(x,y);
            edge_add1(y,x);
            edge_add2(x,y);
            edge_add2(y,x);
        }
    }
    bfs1();
    bfs2();
    int ans=0;
    for(int i=1;i<=n;i++) //枚举每一个点找节点的最大值与最小值差的最大值
    {
        ans=max(ans,maxx[i]-minx[i]);
    }
    printf("%d\n",ans);
    return 0;
}