题解 P1073 【最优贸易】

在想Peach · 2019-04-20 20:14:10 · 题解

由于懒得打一个判断入点的bfs，直接欺负水数据切掉这题。

tarjan+dp？+spfa+并查集。

关于真正完美的做法就是再加一个bfs判1号到的所有点加上入度再拓扑排序dp一下。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int maxn=100005;
stack<int>ql;
int n,m,to[maxn],nxt[maxn],head[maxn],f[maxn],tot,mx[maxn],mn[maxn],dfn[maxn],low[maxn],a[maxn],b[maxn],c[maxn],ansl[maxn];
int p[maxn];
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int find(int x)
{
    if(f[x]==x)return x;
    mx[f[x]]=max(mx[f[x]],mx[x]);//把自己的最值传递上去 
    mn[f[x]]=min(mn[f[x]],mn[x]);
    return f[x]=find(f[x]);
}
void tarjan(int x)
{
    dfn[x]=low[x]=++tot;p[x]=1;ql.push(x);//朴素缩点 
    for(int i=head[x];i;i=nxt[i])
    {
        int g=to[i];
        if(!dfn[g])
        {
            tarjan(g);low[x]=min(low[x],low[g]);
        }
        else if(p[g])low[x]=min(low[x],low[g]);
    }
    if(dfn[x]==low[x])
    {
        while(ql.top()!=x)
        {
            int g=ql.top();
            p[g]=0;f[g]=x;ql.pop();
        }
        ql.pop();p[x]=0;
    }
}
int spfa()
{
    memset(p,0,sizeof(p));
     queue<int>q;
     for(int i=1;i<=n;i++)find(i);
     q.push(f[1]);
     while(!q.empty())//朴素spfa 
     {
        int u=f[q.front()];q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int g=f[to[i]];
            mn[g]=min(mn[u],mn[g]);//更新目前买入最小 
            ansl[g]=max(max(ansl[u],mx[g]-mn[g]),ansl[g]);//用之前买的最少的在这里卖最高价看看可不可以比之前卖的多 
             if(p[g]<=8)//由于数据过水走8次都绰绰有余。。。 
            {
                p[g]++;q.push(g);
            }
         }
     }
     return ansl[f[n]];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>mx[i];f[i]=i;mn[i]=mx[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }
    for(int i=1;i<=m;i++)if(c[i]==2)f[find(a[i])]=find(b[i]);//先把双向边连到一起 
    for(int i=1;i<=m;i++)if(c[i]==1)add(find(a[i]),find(b[i]));//连边 
    tot=0;
    for(int i=1;i<=n;i++)if(!dfn[find(i)])tarjan(find(i));//注意操作的是每一个点的祖先 
    cout<<topo();
}