题解 P2648 【赚钱】

绝顶我为峰 · 2019-07-31 10:18:20 · 题解

我上来一看

这不是板子题吗？

然后又一看

最长路

淦。

还好有SPFA，我们可以把边权取相反数存边，然后跑最短路，输出时再次取相反数就是最长路啦

那么考虑边权是什么

显然，免费路边权是d，收费路边权是d-w（都要取相反数），然后为了节省时间，我们建一个超级源点，和每个点连一条权值为d的边（也要取相反数），然后跑一遍SPFA，如果有负环就输出orz

就是这样啦

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std; 
struct edge
{
    int node,weight;
    edge(int node_,int weight_):
        node(node_),weight(weight_){}
};
vector<edge> v[301];
int d,p,c,f,r[301],dis[301];
bool vis[301];
inline bool SPFA()//板子
{
    memset(dis,127/3,sizeof(dis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    vis[0]=1;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        vis[k]=0;
        ++r[k];
        if(r[k]>c)
            return 1;
        for(vector<edge>::iterator it=v[k].begin();it!=v[k].end();++it)
            if(dis[it->node]>dis[k]+it->weight)
            {
                dis[it->node]=dis[k]+it->weight;
                //cout<<it->node<<" "<<dis[it->node]<<endl;
                if(!vis[it->node])
                {
                    vis[it->node]=1;
                    q.push(it->node);
                }
            }
    }
    return 0;
}
int main()
{
    cin>>d>>p>>c>>f;
    while(p--)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(edge(y,-d));//免费边
    }
    while(f--)
    {
        int x,y,w;
        cin>>x>>y>>w;
        v[x].push_back(edge(y,w-d));//收费边
    }
    for(int i=1;i<=c;++i)
        v[0].push_back(edge(i,-d));//和源点连边
    if(SPFA())
        cout<<"orz\n";//有负环
    else
    {
        int ans=0;
        for(int i=1;i<=c;++i)
            ans=min(ans,dis[i]);//统计
        cout<<-ans<<endl;//再用相反数输出
    }
    return 0;
}