Hdoj 5195 DZY Loves Topological Sorting 【拓扑】+【线段树】

发布时间：2020-12-13 20:42:36 所属栏目：PHP教程来源：网络整理

导读：DZY Loves Topological Sorting Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 922 Accepted Submission(s): 269 Problem Description A topological sort or topological ordering of a direc

DZY Loves Topological Sorting

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

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,u comes 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).

题意：给你n条边，删去不多于K条边，使输出的字典序最大！！
策略：我们每次都找小于等于当前K的较大的数输出就行了，
需明白：1，每减去1个入度都是减去1条边。
2：找到1个点以后，1定要将对应点的入度变成最大值，以防后面还有可能被找到。
代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
const int M = 1e5+5;
const int INF = 0x3f3f3f3f;
using namespace std;

int c[M<<2],in[M];
vector<int > m[M];
vector<int > ans;
int n,mm,k;

void update(int p,int x,int l,int r,int pos){
    if(l == r){
        c[pos] = x; return ;
    }
    int mid = (l+r)>>1;
    if(p <= mid) update(p,x,l,mid,pos<<1); //left和right都是代表的对应的点。
    else update(p,mid+1,r,pos<<1|1);
    c[pos] = min(c[pos<<1],c[pos<<1|1]);
}

int query(int l,int pos){
    if(l == r) return l;
    int mid = (l+r)>>1;
    if(c[pos<<1|1] <= k) return query(mid+1,pos<<1|1);//每次都是尽可能选比较大的点
    return query(l,pos<<1);
}

void topo(){
    for(int i = 0; i < n; ++ i){
        int temp = query(1,n,1);
        k -= in[temp];//表示去掉几个点
        ans.push_back(temp);
        update(temp,INF,1,1); //找到后就要更新
        in[temp] = INF; //1定要变成正无穷
        for(int i = 0; i < m[temp].size(); ++ i){
            int v = m[temp][i];
            --in[v]; 
            update(v,in[v],1);
        }

    }
}

int main(){
    while(scanf("%d%d%d",&n,&mm,&k) == 3){
        for(int i = 0; i <= n; ++ i){
            m[i].clear(); in[i] = 0;
        }
        int u,v;
        for(int i = 0; i < mm; ++ i){
            scanf("%d%d",&u,&v);
            ++in[v];
            m[u].push_back(v);
        }
        for(int i = 1; i <= n; ++ i){
            update(i,in[i],1);
        }
        ans.clear();
        topo();
        printf("%d",ans[0]);
        for(int i = 1; i < n; ++ i)
            printf(" %d",ans[i]);
        printf("
");
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!