题解 P1073 【最优贸易】

90182si · 2019-05-05 02:37:52 · 题解

表示不会spfa,平生只会dp

cin>>x>>y>>z;
c[y-1].push_back(x-1);
if(z==2)c[x-1].push_back(y-1);

对于样例输入，我是反过来存储的（y在前），表示从哪个城市可以把东西买过来卖掉， 例如1 2 1，就说明2城市可以从1城市把东西买过来卖掉

m[i]=max(m[i],v[i]-v[*it]+m[*it]);

• 以2号城市为例子：可以从1、3号城市买东西过来卖掉， 如果2城市的价格大于1城市的价格，就可以交易，利益存到m里面，

• 最终2城市从3城市买东西过来卖掉可以获得最大利益2. 对于这样一个例子：

  3 2
  1 3 5
  1 2 1
  2 3 1

  应该从1城市买，3城市卖掉。

开始的时候，2城市获利为2，计算3城市的时候要加上2城市获利，3城市获利4， 所以式子里面要加上m[*it]

ans[i]=max(ans[i],max(ans[*it],m[*it]));

• ans数组保存从1-N城市所获利润的总和

最后献上22行代码(534ms, 5432KB)，压行真爽

#include <bits/stdc++.h>
using namespace std;
int v[100005],m[100005],ans[100005];
vector<int> c[100005];
vector<int>::iterator it;
int main()
{
    int i=0,N,M,x,y,z;  
    for(cin>>N>>M;i<N;i++)cin>>v[i];
    for(i=0;i<M;i++){
        cin>>x>>y>>z;
        c[y-1].push_back(x-1);
        if(z==2)c[x-1].push_back(y-1);
    }
    for(i=0;i<N;i++)
        for(it=c[i].begin();it!=c[i].end();it++){
            m[i]=max(m[i],v[i]-v[*it]+m[*it]);
            ans[i]=max(ans[i],max(ans[*it],m[*it]));
        }
    cout<<ans[N-1]<<endl;
    return 0;
}