洛谷 P2648 赚钱

这道题其实就是求最长路顺便再判断一下正环而已。

这种题肯定要用SPFA的啦，有又正边权（因为最长路所以正边就相当于负边），又是正环（同理，相当于负环），SPFA专治这种问题。

当一个点入队多次的时候，说明就形成了一个环，在这个地方一直更新，所以当一个点入队超多n次时，就判定为环。

#include <bits/stdc++.h>

using namespace std;

int v , n , m1 , m2 , ans = -1;

int dis[1000010] , vis[1000010] , vvis[1000010];

vector<pair<int , int> > e[1000010];

void work(int st){

	memset(dis , 0 , sizeof(dis));

	memset(vis , 0 , sizeof(vis));

	memset(vvis , 0 , sizeof(vvis));

	queue<int> q;

	dis[st] = v;

	vis[st] = 1;

	vvis[st]++;

	q.push(st);

	while(!q.empty()){

		int x = q.front();

		q.pop();

		vis[x] = 0;

		for(int i = 0; i < e[x].size(); i++){

			int y = e[x][i].first , w = e[x][i].second;

			if(dis[y] < dis[x] + w){

				dis[y] = dis[x] + w;

				if(vvis[y] > n) return;

				if(!vis[y]){

					vis[y] = 1;

					vvis[y]++;

					q.push(y);

				}

			}

		}

	}

	for(int i = 1; i <= n; i++) ans = max(ans , dis[i]);

}

int main(){

	cin >> v >> m1 >> n >> m2;

	for(int i = 1; i <= m1; i++){

		int x , y;

		cin >> x >> y;

		e[x].push_back(make_pair(y , v));

	}

	for(int i = 1; i <= m2; i++){

		int x , y , z;

		cin >> x >> y >> z;

		e[x].push_back(make_pair(y , v - z));

	}

	for(int i = 1; i <= n; i++) work(i);

	if(ans == -1) cout << "orz";

	else cout << ans;

	return 0;

}

双倍经验：Job Hunt S

真的一模一样啊，就输入改了点。