DZY Loves Topological Sorting

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1250 Accepted Submission(s): 403

Problem Description

A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u→v) from vertex u to vertex v, ucomes before v in the ordering.
Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at most k edges from the graph.

Input

The input consists several test cases. (TestCase≤5)
The first line, three integers n,m,k(1≤n,m≤105,0≤k≤m).
Each of the next m lines has two integers: u,v(u≠v,1≤u,v≤n), representing a direct edge(u→v).

Output

For each test case, output the lexicographically largest topological ordering.

Sample Input

5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3

Sample Output

5 3 1 2 4
1 3 2

Hint

Case 1.
Erase the edge (2->3),(4->5).
And the lexicographically largest topological ordering is (5,3,1,2,4).

思路：

用线段树维护区间最小值。

ps.之前没在查询操作加个pushup，一直跑不出答案，因为在查询过程中，sum的值是更新了的，所以要pushup下

实现代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define mid int m = (l + r) >> 1

const int M = 2e5+;

const int inf = 0x3f3f3f3f;

int n,m,cnt,key;

vector<int>g[M];

int sum[M<<],du[M];

void pushup(int rt){

    sum[rt] = min(sum[rt<<],sum[rt<<|]);

}

void build(int l,int r,int rt){

    if(l == r){

        sum[rt] = du[l];

        return;

    }

    mid;

    build(lson);

    build(rson);

    pushup(rt);

}

void update(int p,int l,int r,int rt){

    if(l == r){

        sum[rt]--;

        return ;

    }

    mid;

    if(p <= m) update(p,lson);

    else  update(p,rson);

    pushup(rt);

}

void query(int l,int r,int rt){

    if(l == r){

        cnt -= sum[rt];

        key = l;

        sum[rt] = inf;

        return ;

    }

    mid;

    if(sum[rt<<|] <= cnt) query(rson);

    else query(lson);

    pushup(rt);

}

int main(){

    int u,v;

    while(cin>>n>>m>>cnt){

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

            cin>>u>>v;

            g[u].push_back(v);

            du[v]++;  //入度

        }

        build(,n,);

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

            query(,n,);

            if(i==) cout<<key;

            else cout<<" "<<key;

            for(int j = ;j < g[key].size();j++){

                int x = g[key][j];

                update(x,,n,);

            }

        }

        cout<<endl;

        memset(du,,sizeof(du));

    }

    return ;

}

巴特西

hdu 5195 DZY Loves Topological Sorting （拓扑排序+线段树）

DZY Loves Topological Sorting

最新文章

热门文章