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

时间：2021-09-19 01:54:01

DZY Loves Topological Sorting

Time Limit: 1 Sec  Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5195

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

题意

一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v) 从 u 到 v，都满足u在排列中出现在v之前。
现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。

题解：

因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边，那么我们一定会把当前还没入队的di≤k的最大的i找出来，把它的di条入边都删掉，然后加入拓扑序列。可以证明，这一定是最优的。
具体实现可以用线段树维护每个位置的di，在线段树上二分可以找到当前还没入队的di≤k的最大的i。于是时间复杂度就是O((n+m)logn).

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

int du[];

int vis[];

vector<int> lin[];

int n,m,k;

int t[];

int arr[];

void build(int i,int l,int r)

{

    if (l==r)

    {

        t[i]=du[l];

        arr[l]=i;

        return;

    }

    int mid=(l+r)/;

    build(i*,l,mid);

    build(i*+,mid+,r);

    t[i]=min(t[i*],t[i*+]);

    return;

}

int query(int i,int l,int r,int k)

{

    if (l==r)

        return l;

    int mid=(l+r)/;

    if (t[i*+]<=k) return query(i*+,mid+,r,k);

    else return query(i*,l,mid,k);

}

void insert(int i,int l,int r,int wei,int cc)

{

    if (l==r)

    {

        t[i]+=cc;

        return;

    }

    int mid=(l+r)/;

    if (wei<=mid) insert(i*,l,mid,wei,cc);

    else insert(i*+,mid+,r,wei,cc);

    t[i]=min(t[i*],t[i*+]);

    return;

}

int main()

{

    while (cin>>n>>m>>k)

    {

        memset(vis,,sizeof(vis));

        memset(du,,sizeof(du));

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

            lin[i].clear();

        int i,j;

        for (int tt=;tt<=m;tt++)

        {

            scanf("%d%d",&i,&j);

            lin[i].push_back(j);

            du[j]++;

        }

        int nn=;

        int flag=;

        build(,,n);

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

        {

            int c=query(,,n,k);

            if (flag) printf(" ");

            printf("%d",c);

            flag=;

            k-=du[c];

            insert(,,n,c,);

            for (int kk=;kk<lin[c].size();kk++)

            {

                int j=lin[c][kk];

                insert(,,n,j,-);

                du[j]--;

            }

        }

        printf("\n");

    }

}

相关文章