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

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

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

Sample Output

5 3 1 2 4
1 3 2

HINT

题意

DZY有一张有向无环图(DAG),你要在最多删去k条边之后，求出字典序最大的拓扑序列。

图的拓扑序：

一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v) 从 u 到 v，都满足u在排列中出现在v之前。

题解：

定义k为可以删除的边的上限

我一开始先考虑k=0的情况(即没有边被删)，这样我想可以先加一个虚点，连接每一个入度为０的点，然后从这个虚点开始dfs，每次将边按照连接点的大小排序，然后依次扫描，如果其入度为１就继续dfs,否则其入度减一。

顺着这个思路我发现，完全不知道删除哪条边。所以只能弃疗了。

看了题解发现了一种神奇的方法。我们可以贪心地将具有某种特质的点放入队列中，然后这个队列就是我们要求的拓扑序列。

所需特质是什么呢？

１．它的入度<=k（这样只要切断所有入边，它就可以入队啦）

２．满足１的条件下编号最大的点

那么我们就可以用线段树来维护了，先建一个(1，n)的线段树，记录入度最小值，问题转化成位置最右边的权值小于等于k所在的位置。

这就是个经典模型了。没做过也没关系，其实很简单，只要判断k和右子树的最小值的关系即可，如果k更大，那么答案在右子树，否则在左子树。

最后注意一下，每次找到一个点入队，要把所有出边所在的点入度减一。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200050
 4 #define INF 123456789
 5 int n,m,k,w[N];
 6 vector<int>G[N];
 7 struct Tree{int l,r,min;}tr[N<<2];
 8 template<typename T>void read(T &x)
 9 {
10   int k=0;char c=getchar();
11   x=0;
12   while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
13   if(c==EOF)exit(0);
14   while(isdigit(c))x=x*10+c-'0',c=getchar();
15   x=k?-x:x;
16 }
17 void push_up(int x)
18   {
19     tr[x].min=min(tr[x<<1].min,tr[x<<1|1].min);
20   }
21 void bt(int x,int l,int r)
22 {
23   tr[x].l=l;tr[x].r=r;
24   if (l==r)
25     {
26       tr[x].min=w[l];
27       return;
28     }
29   int mid=(l+r)>>1;
30   bt(x<<1,l,mid);
31   bt(x<<1|1,mid+1,r);
32   push_up(x);
33 }
34 int query(int x)
35 {
36   if (tr[x].min>k)return -1;
37   if (tr[x].l==tr[x].r)
38     {
39       k-=tr[x].min;
40       tr[x].min=INF;
41       return tr[x].l;
42     }
43   int tp=query(x<<1|1);
44   if (tp==-1)tp=query(x<<1);
45   push_up(x);
46   return tp;
47 }
48 void add(int x,int p)
49 {
50   if (p<=tr[x].l&&tr[x].r<=p)
51     {
52       tr[x].min--;
53       return;
54     }
55   int mid=(tr[x].l+tr[x].r)>>1;
56   if (p<=mid)add(x<<1,p);
57   if (mid<p)add(x<<1|1,p);
58   push_up(x);
59 }
60 void work()
61 {
62   read(n);read(m);read(k);
63   memset(w,0,sizeof(w));
64   int x,y;
65   for(int i=1;i<=m;i++)
66     {
67       read(x);read(y);
68       w[y]++;
69       G[x].push_back(y);
70     }
71   bt(1,1,n);
72   int cas=0;
73   for(int i=1;i<=n;i++)
74     {
75       int x=query(1);
76       if (cas++)printf(" ");
77       printf("%d",x);
78       for(int i=0;i<G[x].size();i++)
79     add(1,G[x][i]);
80     }
81   printf("
");
82   for(int i=1;i<=n;i++)G[i].clear();
83 }
84 int main()
85 {
86   #ifndef ONLINE_JUDGE
87   freopen("aa.in","r",stdin);
88   #endif
89   while(1)
90     {
91       work();
92     }
93 }

View Code