现在的位置: 首页 > 综合 > 正文

POJ 3249 Test for Job

2019年04月09日 ⁄ 综合 ⁄ 共 2270字 ⁄ 字号 评论关闭

大意:一个人去找工作遇到了一道面试题,面试官要求给出一些城市和城市之间的道路,每到达一个城市,可能会赚一些钱,但是也可能会有损失。最终面试者的所得会决定他是否能得到这份工作,显而易见,越多越好。

思路:

(1)本题的数据量巨大,虽说是一道5s的题目,但是有100000个城市,1000000条道路,这就要求算法的复杂度至少O(nlogn)或者O(m)以下才不会超时。

(2)结合题意的描述可知,图一定是无环的。

(3)本题给出的是点权图,一般的算法都是基于边权而不是点权,而不是边权图,需要将点权转换为边权。

(4)本题求的是最长路径,而不是最短路径。

对以上问题,我们来一一解答。

首先考虑(3),怎样将点权转换为边权,我们可以这样处理,直接对于每条边权赋值,权值为该边终点的点权,例如<u,v>则边权cost<u,v>为w[v],没有入边的点需要特殊处理,即增加一个新的节点C,然后以C连接入度为0的点,使该边边权为该点点权。具体的证明略。

考虑(4),最长路径,怎么搞?我们将Dijkstra变形即可,即d[i]初始值赋值为-INF,更新的时候大于变小于即可。

考虑(1),数据量大,SPFA或者Dijkstra + heap必定超时。怎么弄?结合(2),即DAG图,有向无环图,那么我们可以通过topsort来优化算法,然后通过DAGShortestPath来求最长路径。具体的算法步骤以及证明请进我的另一篇博客:http://blog.csdn.net/wall_f/article/details/8204747

总结,通过toposort来优化最长路径算法,时间复杂度为O(m),增加一个超级源点0,做一遍最长路径,然后枚举终点的最大值即可。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;

const int MAXN = 100010;
const int MAXM = 1000010;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int v;
	LL w;
	int next;
}edge[MAXM];

int n, m;
int cnt, tot;
int count2;

LL d[MAXN], w[MAXN];
int first[MAXN];
int fa[MAXN], topo[MAXN];
int ind[MAXN], outd[MAXN];
int save[MAXN];

void init()
{
	cnt = 0;
	tot = 0;
	count2 = 0;
	memset(first, -1, sizeof(first));
	memset(fa, 0, sizeof(fa));
	memset(ind, 0, sizeof(0));
	memset(outd, 0, sizeof(outd));
}

void read_graph(int u, int v, LL w)
{
	edge[cnt].v = v, edge[cnt].w = w;
	edge[cnt].next = first[u], first[u] = cnt++;
}

void toposort() //toposort
{
	queue<int> q;
	for(int i = 0; i <= n; i++) if(!ind[i]) q.push(i);
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		topo[++tot] = x;
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v;
			if(--ind[v] == 0)
			{
				q.push(v);
			}
		}
	}
}

void DAGShortestPath(int src) //DAG有向无环图的最长路径
{
	for(int i = 0; i <= n; i++) d[i] = (i == src)? 0:-INF;
	for(int u = 1; u <= tot; u++)
	{
		int x = topo[u];
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v, w = edge[e].w;
			if(d[v] < d[x] + w)
			{
				d[v] = d[x] + w;
				fa[v] = u;
			}
		}
	}
}

void read_case()
{
	init();
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &w[i]);
	}
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		read_graph(u, v, w[v]); //点权转换为边权 
		outd[u]++;
		ind[v]++;
	}
	for(int i = 1; i <= n; i++)
	{
		if(!outd[i]) //储存出度为0的点,即终点
		{
			save[count2++] = i;
		}
		if(!ind[i])
		{
			read_graph(0, i, w[i]); //没有入边的点需要添加一个节点0,并连接一条有向边。 
			ind[i]++;
		}
	}
}

void solve()
{
	read_case();
	toposort();
	DAGShortestPath(0);
	LL ans = -INF;
	for(int i = 0; i < count2; i++) //枚举最大值 
	{
		ans = max(ans, d[save[i]]);
	}
	
	printf("%lld\n", ans);
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		solve();
	}
	return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.