HDU - 5695 Gym Class （优先队列+拓扑排序）

题意：有N个人，每个人的ID为1~N，部分同学A不希望部分同学B排在他之前，排好队之后，每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。在满足这个前提的情况下，将N个人排成一队，求所有同学评价分数和的最大值。

分析：

1、A不希望B排在他之前，所以B要排在A之后，也就是说A安排好后才能安排B，即A对B是一种限制，显然拓扑排序。

2、因为每个同学会找出包括自己在内的前方所有同学的最小ID，作为自己评价这堂课的分数。因此ID大的同学越靠前，最后能得出的分数和越大，因此优先队列。

3、预处理每个人的入度，如果A对B有限制，则B的入度加1。

4、将入度为0的点加入优先队列，并将该点所限制的点入度-1。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 100000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

priority_queue<int> q;

vector<int> v[MAXN];

vector<int> ans;

int indegree[MAXN];

void init(){

    while(!q.empty()) q.pop();

    for(int i = 0; i < MAXN; ++i) v[i].clear();

    ans.clear();

    memset(indegree, 0, sizeof indegree);

}

void deal(int x){

    int len = v[x].size();

    for(int i = 0; i < len; ++i){

        --indegree[v[x][i]];

        if(!indegree[v[x][i]]) q.push(v[x][i]);

    }

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        init();

        int n, m;

        scanf("%d%d", &n, &m);

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

            int a, b;

            scanf("%d%d", &a, &b);

            v[a].push_back(b);

            ++indegree[b];

        }

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

            if(!indegree[i]){

                q.push(i);

            }

        }

        while(!q.empty()){

            int tmp = q.top();

            ans.push_back(tmp);

            q.pop();

            deal(tmp);

        }

        int len = ans.size();

        int _min = INT_INF;

        LL tot = 0;

        for(int i = 0; i < n; ++i){

            _min = min(_min, ans[i]);

            tot += LL(_min);

        }

        printf("%lld\n", tot);

    }

    return 0;

}

巴特西

HDU - 5695 Gym Class （优先队列+拓扑排序）

最新文章

热门文章