文章

68

粉丝

691

获赞

26

访问

576.6k

头像
拓扑排序-反向建图
P1536 清华大学2019年机试题
发布于2020年5月28日 12:45
阅读数 11.2k

拓扑排序求出最早完成时间和所有任务的最早开始时间,然后反向建图,求出最晚开始时间,两遍拓扑

 

#define ll long long
#define vec vector<ll>
#define inf 0x3f3f3f3f
#define MAX 500005
#define P pair<ll,ll>
#define MOD 1000000007

int main() {
	ll m, n, a[MAX], ind[MAX], x[MAX], y[MAX], f[MAX], g[MAX];
	vec G[MAX];
	while (cin >> n >> m) {
		memset(ind, 0, sizeof(ind));
		memset(f, 0, sizeof(f));
		fill(g, g + MAX, inf);
		for (int i = 1; i <= n; i++)cin >> a[i], G[i].clear();
		for (int i = 1; i <= m; i++) {
			cin >> x[i] >> y[i]; ind[y[i]]++; G[x[i]].push_back(y[i]);
		}
		queue<int> q;
		int u = -1, v = -1; ll res = 1, cost = 0;
		//正向跑拓扑,求出所有点最早开始的时间和最小花费
		for (int i = 1; i <= n; i++)if (ind[i] == 0)q.push(i);
		while (!q.empty()) {
			u = q.front(); q.pop();
			for (int i = 0; i < G[u].size(); i++) {
				v = G[u][i]; ind[v]--;
				//所有条件里最长的那个
				if (f[u] + a[u] > f[v])f[v] = f[u] + a[u];
				if (ind[v] == 0) 
					q.push...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发