hdu 5195 DZY Loves Topological Sorting BestCoder Round #35 1002 [ 拓扑排序 + 优先队列 || 线段树 ]
DZY Loves Topological Sorting
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 221 Accepted Submission(s): 52
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.
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) .
Problem B - DZY Loves Topological Sorting 因为我们要求最后的拓扑序列字典序最大,所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边,那么我们一定会把当前还没入队的di≤k的最大的i找出来,把它的di条入边都删掉,然后加入拓扑序列。可以证明,这一定是最优的。 具体实现可以用线段树维护每个位置的di,在线段树上二分可以找到当前还没入队的di≤k的最大的i。于是时间复杂度就是O((n+m)logn).
不过,这里面说的还有一点不太清楚,
转一下另一个题解:
http://blog.csdn.net/glqac/article/details/44710897
看题意以为是个拓扑排序。事实上,就是个线段树。因为最多可以删k条边, 所以就是在线段树里找入度小于等于k的最大值,那么保存个区间最小就ok了。如果右子树的区间最小小于等于k那么就往右边走,因为是要找字典序最大的。当k是0,也是这样找,就跟topological sort是一样的。然后删除一个点就在线段树那个点置最大值,再删除他的边。因为总共也就m条边不超过10^5。
总复杂度o(n+m)logn。
我的解法:
用优先队列,当前节点的入度小于k便入队列,出队列时以节点编号为优先权,如果小于等于k,则输出,反之,跳过。不过写的时候遇到几个问题:
1.节点重复入队列没事,但是,不能让已经在队列中的再入队列。故要用vis,vis=0暂时不在队列中,vis=-1,在队列中,vis=1,已经输出。
2.判断队首元素的入度是否 小于k时,要用现在的入度,而不是入队列时的入度,因为,可能在处理其它点的时候,该点的入度已经发生了变化。
总的来说,还是线段树的方法思路清晰~~
13278084 | 2015-03-29 08:49:19 | Accepted | 5195 | 561MS | 6988K | 2158 B | C++ | czy |
13278083 | 2015-03-29 08:49:04 | Time Limit Exceeded | 5195 | 2000MS | 8308K | 2158 B | G++ | czy |
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <vector> 5 #include <map> 6 #include <algorithm> 7 #include <queue> 8 9 #define ll long long 10 int const N = 100005; 11 int const M = 205; 12 int const inf = 1000000000; 13 ll const mod = 1000000007; 14 15 using namespace std; 16 17 int n,m; 18 int k; 19 int vis[N]; 20 vector<int> bian[N]; 21 int r[N]; 22 23 struct node 24 { 25 friend bool operator < (node n1,node n2) 26 { 27 return n1.index < n2.index; 28 } 29 int index; 30 int d; 31 }; 32 33 void ini() 34 { 35 int u,v; 36 memset(r,0,sizeof(r)); 37 memset(vis,0,sizeof(vis)); 38 int i; 39 for(i=0;i<=n;i++){ 40 bian[i].clear(); 41 } 42 for(i=1;i<=m;i++){ 43 scanf("%d%d",&u,&v); 44 r[ v ]++; 45 bian[ u ].push_back( v ); 46 } 47 48 } 49 50 void solve() 51 { 52 node te,nt; 53 int i; 54 priority_queue<node> que; 55 for(i=n;i>=1;i--){ 56 if(r[ i ]<=k){ 57 te.index=i; 58 te.d=r[i]; 59 que.push(te); 60 vis[i]=-1; 61 } 62 } 63 64 int ff=0; 65 vector<int>::iterator it; 66 while(que.size()>=1){ 67 te=que.top(); 68 que.pop(); 69 // printf(" \nu=%d r=%d k=%d\n",te.index,te.d,k); 70 if(r[te.index]<=k){ 71 k-=r[te.index]; 72 vis[te.index]=1; 73 } 74 else{ 75 vis[te.index]=0; 76 continue; 77 } 78 if(ff==0){ 79 ff=1; 80 printf("%d",te.index); 81 } 82 else{ 83 printf(" %d",te.index); 84 } 85 for(it=bian[te.index].begin();it!=bian[te.index].end();it++) 86 { 87 int y=*it; 88 r[y]--; 89 if(r[y]<=k && vis[y]==0){ 90 nt.index=y; 91 nt.d=r[y]; 92 que.push(nt); 93 vis[y]=-1; 94 } 95 } 96 } 97 printf("\n"); 98 } 99 100 void out() 101 { 102 103 } 104 105 int main() 106 { 107 //freopen("data.in","r",stdin); 108 //freopen("data.out","w",stdout); 109 //scanf("%d",&T); 110 //for(int cnt=1;cnt<=T;cnt++) 111 //while(T--) 112 while(scanf("%d%d%d",&n,&m,&k)!=EOF) 113 { 114 ini(); 115 solve(); 116 out(); 117 } 118 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。