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, x, mid+1, r, pos<<1|1);
c[pos] = min(c[pos<<1], c[pos<<1|1]);
}
int query(int l, int r, int pos){
if(l == r) return l;
int mid = (l+r)>>1;
if(c[pos<<1|1] <= k) return query(mid+1, r, pos<<1|1);//每次都是盡可能選比較大的點
return query(l, mid,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, n, 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, n, 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, n, 1);
}
ans.clear();
topo();
printf("%d", ans[0]);
for(int i = 1; i < n; ++ i)
printf(" %d", ans[i]);
printf("
");
}
return 0;
} 
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
