洛谷 P1073 NOIp2009提高组 最优贸易 题解【拓扑排序】【tarjan】

点击量：122

    万年巨坑终于被填上了……

目录

题目描述

\(C\)国有\(n\)个大城市和\(m\)条道路，每条道路连接这\(n\)个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这\(m\)条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为\(1\)条。

 

\(C\)国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

 

商人阿龙来到\(C\)国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设\(C\)国\(n\)个城市的标号从\(1\sim n\)，阿龙决定从\(1\)号城市出发，并最终在\(n\)号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有\(n\)个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来\(C\)国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

 

假设\(C\)国有\(5\)个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设\(1\sim n\)号城市的水晶球价格分别为\(4,3,5,6,1\)。

 

阿龙可以选择如下一条线路：\(1\rightarrow 2\rightarrow 3\rightarrow 5\)，并在\(2\)号城市以\(3\)的价格买入水晶球，在\(3\)号城市以\(5\)的价格卖出水晶球，赚取的旅费数为\(2\)。

 

阿龙也可以选择如下一条线路\(1\rightarrow 4\rightarrow 5\rightarrow 4\rightarrow 5\)，并在第\(1\)次到达\(5\)号城市时以\(1\)的价格买入水晶球，在第\(2\)次到达\(4\)号城市时以\(6\)的价格卖出水晶球，赚取的旅费数为\(5\)。

 

现在给出\(n\)个城市的水晶球价格，\(m\)条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

 

输入输出格式

输入格式：

第一行包含\(2\)个正整数\(n\)和\(m\)，中间用一个空格隔开，分别表示城市的数目和道路的数目。

 

第二行\(n\)个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这\(n\)个城市的商品价格。

 

接下来\(m\)行，每行有\(3\)个正整数\(x,y,z\)，每两个整数之间用一个空格隔开。如果\(z=1\)，表示这条道路是城市\(x\)到城市\(y\)之间的单向道路；如果\(z=2\)，表示这条道路为城市\(x\)和城市\(y\)之间的双向道路。

 

输出格式：

一 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出\(0\)。

 

输入输出样例

输入样例#1：

5 5 
4 3 5 6 1 
1 2 1 
1 4 1 
2 3 2 
3 5 1 
4 5 2 

输出样例#1：

5

说明

【数据范围】

输入数据保证\(1\)号城市可以到达\(n\)号城市。

 

对于\(10\%\)的数据，\(1\le n\le 6\)。

对于\(30\%\)的数据，\(1\le n\le 100\)。

对于\(50\%\)的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。

对于\(100\%)的数据，\(1≤n≤100000,1\le m\le 500000,1\le x,y\le n,1\le z\le 2,1\le\)各城市水晶球价格\(\le 100\)。

题解：

    这个题就是问1号点能到达的所有能到达终点的点中，价格与这个点之差的最大值。实际上，使用拓扑排序可以很快地理清楚可达性。但是这个题会有环和无向边，不能直接做拓扑排序。如果用简单的bfs，时间复杂度会达到\(O(n^2)\)，而我们要进行拓扑排序，就要把图变成一个DAG。

    把图变成DAG最简单的方法就是tarjan缩强连通分量为点，感觉比较可做。但是每个点的价格是唯一的，因此缩点时还要统计这个强连通分量中最大的价格和最小的价格，因为这两个价格代表的点总是可以互达，因此我们贪心地认为在这个大点购买所花费的价格是这个最小值，所卖出的价格是最大值。同时还要让它可以被\(1\)点到达，且能到达\(n\)点，那么就可以做反向拓扑排序，记录来时的最大值（此时来路有很多种，要选择更大的一条），减去这里的价格，更新答案。最后只需要把\(1\)号点能到达的点的答案统计好就可以了。

Code：

#include<cstdio>
#include<cstring>
struct edge
{
    int from,n,nxt;
    edge(int from,int n,int nxt)
    {
        this->from=from;
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[1000000];
int head[100100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(from,to,head[from]);
    head[from]=ecnt;
}
int s[100100],del[100100],top=0,dfn[100100],low[100100],cnt=0;
bool in[100100];
int mx[100100],mn[100100];//一个点的最大值和最小值
void tarjan(int x)//缩点
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    in[x]=1;
    s[++top]=x;
    for(int i=head[x];~i;i=e[i].nxt)
        if(in[e[i].n])
            low[x]=low[x]<dfn[e[i].n]?low[x]:dfn[e[i].n];
        else if(!dfn[e[i].n])
        {
            tarjan(e[i].n);
            low[x]=low[x]<low[e[i].n]?low[x]:low[e[i].n];
        }
    if(low[x]==dfn[x])
    {
        do
        {
            del[s[top]]=x;
            mx[x]=mx[x]>mx[s[top]]?mx[x]:mx[s[top]];
            mn[x]=mn[x]<mn[s[top]]?mn[x]:mn[s[top]];
            in[s[top--]]=0;
        }while(s[top+1]!=x);
    }
    return;
}
int ind[100100];
int q[100100],l=0,r=0;
bool ava[100100];
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&mx[i]);
        mn[i]=mx[i];
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v);
        if(w==2)
            add(v,u);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    memset(head,-1,sizeof(head));
    int ocnt=ecnt;
    ecnt=-1;
    for(int i=0;i<=ocnt;++i)//反向建边
        if(del[e[i].from]!=del[e[i].n])
        {
            add(del[e[i].n],del[e[i].from]);
            ++ind[e[ecnt].n];
        }
    for(int i=1;i<=n;++i)
        if(del[i]==i&&!ind[i])
            q[++r]=i;
    ava[del[n]]=1;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)
        {
            ava[e[i].n]|=ava[x];
            ind[e[i].n]--;
            mx[e[i].n]=mx[e[i].n]>mx[x]?mx[e[i].n]:mx[x];
            if(!ind[e[i].n])
                q[++r]=e[i].n;
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        if(ava[i]&&del[i]==i)
            ans=ans>mx[i]-mn[i]?ans:mx[i]-mn[i];
    printf("%d\n",ans);
    return 0;
}