自动搬运

查看原文

来自洛谷，原作者为

	绝顶我为峰 蓝的盆。

搬运于2025-08-24 21:40:02，当前版本为作者最后更新于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;
}