洛谷 P6145 【[USACO20FEB]Timeline G】

这道题难就难在建图吧，建图懂了之后，跑一遍最长路就好了（也就是关键路径，但是不会用拓补排序求qnq，wtcl）。

怎么建图呢？先不管输入的S，看下面的输入，直接建有向边即可，权值为x。如果现在跑最长路的话，没有一个出发点，那是不行的，所以我们可以想到建一个点，去连接一下入度为0的点，边权为多少呢？这就跟S挂钩了，推下样例，很容易发现边权即为输入的S。这个点的其实就叫超级源点，是一个很重要的思想，在这种题里面建超级源点很常见，当然，还有超级汇点，就是把所有出度为0的点连向一个点，这道题还用不上。现在，我们就可以写下最长路啦（因为是最长路所以不能用迪杰斯特拉算法！！！）。

交上去，好，只有80分。为什么呢？

连输入的S都没用完你想得满分？当我们建超级源点时，只向入度为0的点连了边，那么可不可以给其他点连呢？答案是可以的。设\(dis_i\)为超级源点到i的最长路，那么一定有可能\(dis_i\)小于一开始给出的S，这时肯定选择S啊，所以我们可以把超级源点向其他的点连一条S的边，这样就把所有情况考虑完了。

满分代码~

#include <bits/stdc++.h>

using namespace std;

int n , m , c , ans;

int dis[100010] , vis[100010];

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

void spfa(int s){

	vis[s] = 1;	//最长路dis赋值为0

	queue<int> q;

	q.push(s);

	while(!q.empty()){

		int x = q.front();

		q.pop();

		vis[x] = 0;

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

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

			if(dis[nx] < dis[x] + w){	//注意是最长路哦！！！

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

				if(!vis[nx]){

					vis[nx] = 1;

					q.push(nx);

				}

			}

		}

	}

}

int main(){

	cin >> n >> m >> c;

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

		int x;

		cin >> x;

		e[0].push_back(make_pair(i , x));	//建超级源点

	}

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

		int x , y , z;

		cin >> x >> y >> z;

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

	}

	spfa(0);	//从超级源点开始跑，而不是1

	for(int i = 1; i <= n; i++) cout << dis[i] << endl;

	return 0;

}

双倍经验时间：

P1113

巴特西

洛谷 P6145 【[USACO20FEB]Timeline G】

最新文章

热门文章