DZY Loves Topological SortingTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 264Accepted Submission(s): 63
Problem Description
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edgefrom vertexto vertexcomes beforein the ordering.Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at mostedges from the graph.
Input
The input consists several test cases. ()The first line, three integers.Each of the nextlines has two integers:, representing a direct edge.
Output
For each test case, output the lexicographically largest topological ordering.
Sample Input
5 5 21 24 52 43 42 33 2 01 21 3
Sample Output
5 3 1 2 41 3 2
Hint
Case 1.Erase the edge (2->3),(4->5).And the lexicographically largest topological ordering is (5,3,1,2,4).
Source
Recommend
hujie|We have carefully selected several similar problems for you:51975196519351925189
题意：n个点m条有向边组成的有向无环图，可以最多删除k条边让他的拓扑序最大。输出最大的拓扑序。
思路：在以前的topsort中是入读为零的点入队列，这里有k次机会可以删除边，那么我就把所有入度<=k的点全入队列，用优先队列维护最大的点序列号，，去掉点最大序列号的所有入边，将它加入到拓扑序中，这样贪心是最优的。
132784372015-03-29 09:39:39Accepted5195374MS8344K2822 BC++wust_lyf
132784692015-03-29 09:42:51Accepted51951996MS10928K2822 BG++wust_lyf
G++和C++差别如此大
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 200005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;struct Node{int x;int id;friend bool operator<(const Node a,const Node b){return a.id<b.id;}};int n,m,k;vector <int> edge[maxn];priority_queue<Node> Q;int inDegree[maxn];int ans[maxn];int vis[maxn];int main(){int i;while(scanf("%d%d%d",&n,&m,&k)!=EOF){for (i=0;i<=n+2;i++){edge[i].clear();inDegree[i]=0;vis[i]=0; //不在队列中ans[i]=0;}for (i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);inDegree[b]++;edge[a].push_back(b);}while(!Q.empty())Q.pop();Node node;for (i=1;i<=n;i++)if (inDegree[i]<=k){node.id=i;node.x=inDegree[i];Q.push(node);vis[i]=1;//在队列中}int t=0;while (!Q.empty()){Node now=Q.top();Q.pop();if (inDegree[now.id]<=k)k-=inDegree[now.id];else{vis[now.id]=0;continue;}vis[now.id]=2;//已经输出ans[t++]=now.id;for (i=0;i<edge[now.id].size();i++){int v=edge[now.id][i];inDegree[v]–;node.id=v;node.x=inDegree[v];if (inDegree[v]<=k && vis[v]==0){Q.push(node);vis[v]=1;}}}pf("%d",ans[0]);for (int i=1;i<t;i++)pf(" %d",ans[i]);pf("\n");}return 0;}/*6 6 25 61 24 52 43 42 33 2 01 21 3*/
可是旅行的彼时那刻我的心情一直是好的吗？
