白告山风

不定期更新摄影，acm题解等等有趣的东西~

0%

拓扑排序专题（初稿）

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

基本思路：每次寻找一个入度（前驱为0）的点进入答案队列之后，然后所有前驱为它的点的入度减一，然后循环继续找入度为0的点。这里要特别指出，当有向图内存在环的时候，最后查询结束之后，答案队列中的元素个数会少于总共的点数。

例题1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Problem Description
有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。


输入样例
4 3
1 2
2 3
4 3
 
输出样例
1 2 4 3


源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int maxn=508;
int map1[maxn][maxn],indgr[maxn],res[maxn];//map1是邻接矩阵，indgr[i]代表i点位置当前有几个前驱，res为输出数组
int n,m;
void topsort(int n){
	int k=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){//从小到大寻找 
			if(!indgr[j]){//如果当前前驱点数为0， 
				res[i]=j;//记录当前点的编号
				indgr[j]--;
				k=j;//保存当前点 
				break; 
			}
		}
		for(int j=1;j<=n;j++){
			if(map1[k][j]){//删除由当前点开始的所有边 
				map1[k][j]=0;
				indgr[j]--;
			}
		}
	}
}
void opt(int n){
	for(int i=1;i<=n;i++){
		if(i<n)printf("%d ",res[i]);
		else printf("%d\n",res[i]);
	}
} 
int main(){
	while(scanf("%d%d",&n,&m)==2){
		memset(map1,0,sizeof(map1));
		memset(indgr,0,sizeof(int)*(n+1));
		
		for(int i=1;i<=m;i++){
			int p1,p2;
			scanf("%d%d",&p1,&p2);//p1->p2
			if(!map1[p1][p2]){//防止重边 
			map1[p1][p2]=1;
			indgr[p2]++;
			}
		}
		topsort(n);
		opt(n);
	}
	return 0;
}

例题2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Problem Description
甘晨煜是一家软件公司的创始人，人称“甘老板”。

经过几年的努力，公司已经准备在纳斯达克上市，甘老板自然也是心情大好。随着中秋节的临近，甘老板决定为员工们每人发个红包。

现在的问题是，每人发多少红包呢？要知道，很多员工提出了自己的要求，比如，胡承轩就提出他的红包应该比麻致远的大！

为了图吉利，甘老板决定为每名员工至少发888的红包，同时，他还希望能满足员工们提出的所有的要求，当然，最后是希望发出红包的总金额最少。

Input
输入包含多组测试数据。
每组数据第一行首先是两个整数n和m，分别表示员工的人数是n，员工们一共提出了m条要求。
接着的m行，每行包含2个整数a和b，表示一条要求：a的红包应该比b的大。

n<=10000
m<=20000
员工编号a和b不等，且都在区间[1,n]内

Output
对于每组测试数据，请输出甘老板总共最少需要发出多少金额的红包。
如果不能满足员工提出的全部的要求，直接输出-1即可。


输入样例
2 1
1 2
2 2
1 2
2 1
输出样例
1777
-1

源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+6;
int n,m;

vector<int> map1[N];
int indgr[N],money[N];
void topsort(int n){
	int num=0;
	for(int i=1;i<=n;i++){//遍历money 
		int k=0;
		for(int j=1;j<=n;j++){
			if(!indgr[j]){
				indgr[j]--;
				k=j;
				num++;
				break;
			}
		}
		for(int j=0;j<map1[k].size();j++){
			int remain=map1[k][j];
			indgr[remain]--;
			money[remain]=max(money[remain],money[k]+1);
		}
	}
	if(num==n){
		int ans=0;
		for(int i=1;i<=n;i++){
			ans+=888+money[i];
		}
		printf("%d\n",ans);
	}
	else{
		printf("-1\n");
	}
}
int main(){
	while(scanf("%d%d",&n,&m)==2){
		for(int i=1;i<=n;i++){
			map1[i].clear();
		}
		memset(indgr,0,sizeof(int)*(n+1));
		memset(money,0,sizeof(int)*(n+1));
		for(int i=1;i<=m;i++){
			int a,b;
			scanf("%d%d",&a,&b);//b->a 888->889
			map1[b].push_back(a);
			indgr[a]++;
		}
		topsort(n);
	}
	return 0;
}