经典问题----拓扑排序(HDU2647)

题目简介:有个工厂的老板给工人发奖金,每人基础都是888,工人们有自己的想法,如:a 工人想要比 b 工人的奖金高,老板想要使花的钱最少 那么就可以 给b 888,给a 889 ,但是如果在此基础上,b也想比a高,那么就不能让他们满意,输出 -1;输入第一行有两个数字,分别为工人数n和要求数m,接下来m行为a员工要求比b员工奖金高。

思路简介:一般拓扑排序:通过记录邻接表入度,先查找入度为0的点输出,如有多个相同值,则随意输出,然后删除该点与下一点的连接,继续查找入度为0的点,直到全部点输出完毕。但由于本题的层数不定,所以应当将入度改为出度,在这里用反向建边优化,如此的时候,我们在拓扑排序的时候第一次找到的点就是没有要求的工人,那么奖励就直接加888,再考虑这一层之后让基本奖励 + 1 ,再拓扑排序便可以了;

基本代码:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack> using namespace std; #define MAX 10005 struct node
{
int to, next;//to为该边指向的高奖金顶点;next为储存该边的下一条同级边,-1表示没有同级边
}edge[MAX * ]; int head[MAX];//此数组为同级边最靠近低奖金的那条边编号 void add(int a, int b, int tol)
{
edge[tol].to = b;//从奖金小的指向奖金大的
edge[tol].next = head[a];
head[a] = tol;
} int N, M;
int indegree[MAX];//入度
int temp[MAX];//记录临时入度为0点,也就是分析中的在同一层次同一要求奖金额的工人 int topu()
{
int rw = ;//初始奖励
int ans = ;//最后奖励总和
int tol;
for (int i = ; i < N; i += tol)//此为完成所有工人的奖金运算
{
tol = ;//入度为0的点数
int j;
for (j = ; j <= N; j++)//遍历寻找入度为0的点数,即工人数
if (indegree[j] == )
{
temp[tol++] = j;
indegree[j] = -;//取消改点的入度记录
}
if (tol == ) return -;//没有找到就是形成了环,达不到要求
ans += rw*tol; rw++; //这一次入度为0的点数 * 此层的要求奖励额
for (j = ; j<tol; j++)//可达边的删除
{
for (int k = head[temp[j]]; k != -; k = edge[k].next)
{
int v = edge[k].to;
indegree[v]--;
}
}
}
return ans;
} int main()
{
while (~scanf("%d%d", &N, &M))
{
int a, b;
memset(head, -, sizeof(head));
memset(indegree, , sizeof(indegree));
for (int i = ; i < M; i++)
{
scanf("%d%d", &a, &b);
add(b, a, i);//邻接表加边
indegree[a]++;
}
printf("%d\n", topu());
}
return ;
}

HDU2647

上一篇:Nginx实践01-ngnix编译安装-测试


下一篇:Greenplum源码编译安装(单机及集群模式)完全攻略