议事大厅-【赛码网】..

DAG 即 Directed Acyclic Graph, 有向无环图. 用DAG可以描述一些有依赖关系的任务组, 而这些任务还有另外一个属性, 即都有一个权重, 标示这个任务的重要性.

我们需要你来实现一个算法, 对DAG里面的节点进行排序, 保证排序不违背DAG的依赖关系, 即一个任务A如果排在任务B前面, 那么在DAG中不能存在由B 到A的路径. 另外一个要求就是, 让权重大的任务尽量优先执行.

coder_UDHMTDE8

有

2017-09-26 10:53

coder_XNTiY1yz

有啊

2017-09-26 11:01

coder_0m1Sb3Bz

第二题哪位大神分享波思路

2017-09-26 11:07

coder_X4CV9SHR

40%的广度遍历

2017-09-26 11:08

coder_8aPVMgZv

就是记录一下每个结点的入度，每次找到入度为0的点中权重最大的，输出，并将它连着的点的入度值都减去1.

package qunaer;

import java.util.Scanner;
public class Main3 {
    static int[][] graph;
    static int[] countTo;   //记录入度
    static int[] weight;    //权重
    static int n,e;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        e = in.nextInt();

        graph = new int[n+1][n+1];
        weight = new int[n+1];
        countTo = new int[n+1];

        //输入权重
        int seq;
        for (int i=1; i<=n; i++){
            seq = in.nextInt();
            weight[seq] = in.nextInt();
        }

        //输入边，并累加入度
        int s,t;
        for (int i=1; i<=e; i++){
            s = in.nextInt();
            t = in.nextInt();
            graph[s][t] = 1;
            countTo[t] = countTo[t] + 1;
        }

        printAll();

    }
    static void printAll(){
        int printCount = 1;
        while (printCount <= n){
            int maxWeight = 0, index = 0;
            for (int i=1; i<=n; i++){
                if (countTo[i]==0 && weight[i]>=maxWeight){
                    index = i;
                    maxWeight = weight[i];
                }
            }
            if (printCount == n)    System.out.println(index);
            else System.out.print(index + " ");
            countTo[index] = -1;
            for (int i=1; i<=n; i++){
                if (graph[index][i] == 1){
                    countTo[i]--;
                }
            }

            printCount++;
        }
    }
}

2017-09-26 11:09

coder_xz7eIGnG

拓扑排序变了下型，很裸，但是自己代码有个地方写搓了。以下是改过来的代码

#include <bits/stdc++.h>

using namespace std;

struct Edge{
	int from, to;
	int next;
	Edge() {}
	Edge(int from, int to, int next) : from(from), to(to), next(next) {}
};

void addedge(Edge *edges, int *head, int x, int from, int to)
{
	edges[x] = Edge(from, to, head[from]);
	head[from] = x;
}

int main()
{
	int n, e;
	while (~scanf("%d%d", &n, &e)) {
		int *head = (int *)malloc(sizeof(int) * (n + 1));
		int *ans = (int *)malloc(sizeof(int) * n);
        Edge *edges = (Edge *)malloc(sizeof(Edge) * e);
		int *val = (int *)malloc(sizeof(int) * (n + 1));
		bool *vis = (bool *)malloc(sizeof(bool) * (n + 1));
		int *in = (int *)malloc(sizeof(int) * (n + 1));

		for (int i = 1; i <= n; i++)
			head[i] = -1, vis[i] = false, in[i] = 0;

		for (int i = 1; i <= n; i++) {
			int x, v;
			scanf("%d%d", &x, &v);
			val[x] = v;
		}
		for (int i = 0; i < e; i++) {
			int from, to;
			scanf("%d%d", &from, &to);
			addedge(edges, head, i, from, to);
			in[to]++;
		}

		int top = 0;
        while (true) {
			int theMaxVal = 0, sel;
			bool has = false;
			for (int i = 1; i <= n; i++) {
				if (in[i] == 0 && vis[i] == false && theMaxVal < val[i])
					theMaxVal = val[i], sel = i, has = true;
			}
			if (!has)
				break;
			ans[top++] = sel;
			vis[sel] = true;
			int i = head[sel];
			for (; i + 1; i = edges[i].next) {
				int to = edges[i].to;
				in[to]--;
			}
        }

        for (int i = 0; i < top; i++)
			printf("%d%c", ans[i], i == top - 1 ? '\n' : ' ');

		free(head);
		free(ans);
		free(edges);
		free(val);
		free(vis);
		free(in);
	}
	return 0;
}

2017-09-26 11:13