【杭电oj5695】Gym Class ——百度之星初赛

ゝ一世哀愁。 2022-09-25 07:16 145阅读 0赞

# Gym Class #

**Time Limit: 6000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1090 Accepted Submission(s): 437**

Problem Description

众所周知，度度熊喜欢各类体育活动。  
  
今天，它终于当上了梦寐以求的体育课老师。第一次课上，它发现一个有趣的事情。在上课之前，所有同学要排成一列， 假设最开始每个人有一个唯一的ID，从1到  N![Image 1][]，在排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。麻烦的是，有一些同学不希望某个（些）同学排在他（她）前面，在满足这个前提的情况下，新晋体育课老师——度度熊，希望最后的排队结果可以使得所有同学的评价分数和最大。

Input

第一行一个整数  T![Image 1][]，表示  T(1≤T≤30)![Image 1][] 组数据。  
  
对于每组数据，第一行输入两个整数  N![Image 1][]和  M(1≤N≤100000,0≤M≤100000)![Image 1][]，分别表示总人数和某些同学的偏好。  
  
接下来  M![Image 1][]行，每行两个整数  A![Image 1][] 和  B(1≤A,B≤N)![Image 1][]，表示ID为  A![Image 1][]的同学不希望ID为  B![Image 1][]的同学排在他（她）之前。你可以认为题目保证至少有一种排列方法是符合所有要求的。

Output

对于每组数据，输出最大分数 。

Sample Input

3
    1 0
    2 1
    1 2
    3 1
    3 1

Sample Output

1
    2
    6

Source

[2016"百度之星" - 初赛（Astar Round2A） ][2016_ - _Astar Round2A_]

Recommend

wange2014 | We have carefully selected several similar problems for you: [5842][] [5841][] [5840][] [5839][] [5838][]

拓扑排序+优先队列+邻接表。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int N = 100005;
    struct node {
    	int v,next;
    } s[N];
    int head[N],degree[N],a[N];
    int cnt,n,m,temp;
    void add(int a,int b) {
    	s[cnt].v=b;
    	s[cnt].next=head[a];
    	head[a]=cnt++;
    	degree[b]++;
    }
    void topo() {
    	priority_queue<int,vector<int>,less<int> >Q;
    	for(int l=1; l<=n; l++) {
    		if(!degree[l])
    			Q.push(l);
    	}
    	temp=0;
    	while(!Q.empty()) {
    		int top=Q.top();
    		Q.pop();
    		a[temp++]=top;
    		for(int i=head[top]; i!=-1; i=s[i].next) {
    			int v=s[i].v;
    			degree[v]--;
    			if(!degree[v]) {
    				Q.push(v);
    			}
    		}
    	}
    }
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		scanf("%d%d",&n,&m);
    		cnt=0;
    		memset(head,-1,sizeof(head));
    		memset(degree,0,sizeof(degree));
    		for(int i=0; i<m; i++) {
    			int a,b;
    			scanf("%d%d",&a,&b);
    			add(a,b);
    		}
    		topo();
    		int flag=1000000;
    		__int64 ans=0;		//没想到答案超int 哇了一次。 
    		for(int i=0; i<temp; i++) {
    			flag=min(flag,a[i]);
    			ans=ans+flag;
    		}
    		printf("%I64d\n",ans);
    	}
    	return 0;
    }

[题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5695][http_acm.hdu.edu.cn_showproblem.php_pid_5695]

[Image 1]: 
[2016_ - _Astar Round2A_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2016%26quot%3B%B0%D9%B6%C8%D6%AE%D0%C7%26quot%3B+-+%B3%F5%C8%FC%A3%A8Astar+Round2A%A3%A9&source=1&searchmode=source
[5842]: http://acm.hdu.edu.cn/showproblem.php?pid=5842
[5841]: http://acm.hdu.edu.cn/showproblem.php?pid=5841
[5840]: http://acm.hdu.edu.cn/showproblem.php?pid=5840
[5839]: http://acm.hdu.edu.cn/showproblem.php?pid=5839
[5838]: http://acm.hdu.edu.cn/showproblem.php?pid=5838
[http_acm.hdu.edu.cn_showproblem.php_pid_5695]: http://acm.hdu.edu.cn/showproblem.php?pid=5695