【拓扑排序】威虎山上的分配-C++

威虎山上的分配

描述

每年过年的时候，座山雕都会给兄弟们分银子，分银子之前，座山雕允许大伙儿发表意见，因为要是没法满足所有人的意见，指不定谁要搞出什么大新闻。不过每个人在提意见的时候只能说：“我认为 A 分的银子应该比 B 多！”。座山雕决定要找出一种分配方案，满足所有人的意见，同时使得所有人分得的银子总数最少，并且每个人分得的银子最少为 100两。

输入

第一行两个整数 n,m(0<n≤10000,0<m≤20000)，表示总人数和总意见数；

以下 m 行，每行两个整数 a,b，之间用一个空格隔开，表示某个意见认为第 a 号小弟所分得的银两应该比第 b 号小弟多，所有小弟的编号由 1 开始。

输出

若无法找到合法方案，则输出Unhappy!(不包含引号)，否则输出一个数表示最少总银两数。

输入样例 1

3 2

1 2

2 3

输出样例 1

303

来源

计蒜客

这道题就是很典型一道拓扑排序的题目，但是有个坑点“第 a 号小弟所分得的银两应该比第 b 号小弟多”，所以在输入的时候需要把u和v反过来emm其他的话就是基本一个拓扑模板，特判一下有没有有环的情况就可以了（没有用dfs跑一遍）。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAX_N=10000+1;

const int MAX_M=20000+1;

int cnt,money[MAX_N];

bool vis[MAX_N];

struct edge{

	int v,next;

	int len;

}E[MAX_M];

int p[MAX_N],eid=1;

void insert(int u,int v){

	E[eid].v=v;

	E[eid].next=p[u];

	p[u]=eid++;

}

int n,m;

int indegree[MAX_N];

void topo(){

	queue<int> q;

	for(int i=1;i<=n;i++)

	{

		if(indegree[i]==0)

		{

			q.push(i);

		}

	}

	while(!q.empty())

	{

		int now=q.front();

		vis[now]=1;

		cnt++;

		q.pop();

		for(int i=p[now];i!=0;i=E[i].next)

		{

			int v=E[i].v;

			indegree[v]--;

			if(indegree[v]==0)

			{

				q.push(v);

				vis[v]=1;

				//printf("money[%d]=money[%d]+1\n",v,i);

				money[v]=money[now]+1;

			}

		}

	}

}

int main()

{

	memset(indegree,0,sizeof(indegree));

	cin>>n>>m;

	for(int i=1;i<=m;i++){

		int u,v;

		cin>>u>>v;

		insert(v,u);

		indegree[u]++;

	}

	topo();

	int ans=0;

	for(int i=1;i<=n;i++)

	{

		if(!vis[i])

		{

			cout<<"Unhappy!"<<endl;

			return 0;

		}

		//printf("money[%d]=%d\n",i,money[i]);

		ans+=money[i];

	}

	cout<<ans+n*100<<endl;

	return 0;

}

ov.