题解 P1073 【最优贸易】

· · 题解

不带任何高级技巧的搜索+乱搞哈希

适合蒟蒻阅读

First:

我不会链式前向星，但是邻接矩阵肯定会爆，所以用了很神奇的结构体存图

struct point{
    int val;
    int tox;//点的出度
    int to[500];//所连接的点数组
}q[100000];

只存了最多500个点，怕爆空间，可以水过。

Second:

搜索的时候用一个sta变量表示阶段。

通过阅读可得，贸易可以分为三个阶段：

买珠宝、卖珠宝、去终点

由于三个阶段是顺序做的事情，所以可以分别搜索

最后关于判重：乱搞哈希

我搜索时用到的三个变量：现在所在的地点now，拥有的钱money，以及现处阶段sta。于是就乱搞了这个判重语句：

 int hash(int a,int b,int c)
{
    return (a*133%MOD+b*97%MOD+c*17%MOD)%MOD;
}//哈希函数
void dfs(int now,int money,int sta)
{
    int ha=hash(now,money,sta);
    if(HASH[ha]) return ;
    HASH[ha]=true;
    ......
}

完整AC程序

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct point{
    int val;
    int tox;
    int to[500];
}q[100000];
int i,n,m,ans;
int MOD=9999990;
bool HASH[9999990];//哈希判重

void add(int x,int y)
{
    q[x].tox++;q[x].to[q[x].tox]=y;
}
int hash(int a,int b,int c)
{
    return (a*133%MOD+b*97%MOD+c*17%MOD)%MOD;
}
void dfs(int now,int money,int sta)
{
    int j,k;
    int ha=hash(now,money,sta);
    if(HASH[ha]) return ;
    HASH[ha]=true;
    if(now==n&&sta==3)
    {
        if(money>ans) ans=money;
        return ;
    }//到达终点
    if(sta==1)
    {
        for(j=1;j<=q[now].tox;j++)
        {
            //在这里买
            dfs(q[now].to[j],q[now].val,2);
            //不在这里买 
            dfs(q[now].to[j],money,1);
        }
    }
    else if(sta==2) //卖 
    {
        for(j=1;j<=q[now].tox;j++)
        {
            //在这里卖 
            if(q[now].val-money>ans) 
            dfs(q[now].to[j],q[now].val-money,3);
            //不卖 
            dfs(q[now].to[j],money,2);
        }
    }
    else
    {
        for(j=1;j<=q[now].tox;j++)
        dfs(q[now].to[j],money,3);
    }//去终点
    return ;
}
int main()
{
    cin>>n>>m;  
    for(i=1;i<=n;i++)
    cin>>q[i].val;
    for(i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y);
        if(z==2) add(y,x); 
    }

    dfs(1,0,1);
    cout<<ans;
}