题目地址：HDU 5195 简直受不了了。。BC第二题都开始线段树+拓扑排序了。。。 这题很容易想到拓扑排序过程中贪心，但是贪心容易TLE，，所以需要用数据结构去维护，我用的是线段树维护。每次找入度小于等于k的编号最大的点，这样就可以保证字典序一定是最大的。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int deg[MAXN], head[MAXN], cnt, c[MAXN], Min[MAXN<<2];<int>vec;int k, n;struct node {int u, v, next;} edge[MAXN];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void init(){memset(head,-1,sizeof(head));memset(deg,0,sizeof(deg));cnt=0;}void PushUp(int rt){Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);}void Update(int p, int x, int l, int r, int rt){if(l==r){Min[rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(p,x,lson);else Update(p,x,rson);PushUp(rt);}int Query(int l, int r, int rt){if(l==r) return l;int mid=l+r>>1;if(Min[rt<<1|1]<=k) return Query(rson);return Query(lson);}void topo(){int i, j, id;for(i=0;i<n;i++){id=Query(root);k-=deg[id];deg[id]=INF;Update(id,INF,root);vec.push_back(id);for(j=head[id];j!=-1;j=edge[j].next){int v=edge[j].v;deg[v]–;Update(v,deg[v],root);}}}int main(){int m, i, j, u, v;while(scanf(“%d%d%d”,&n,&m,&k)!=EOF) {vec.clear();init();while(m–) {scanf(“%d%d”,&u,&v);deg[v]++;add(u,v);}for(i=1;i<=n;i++){Update(i,deg[i],root);}topo();for(i=0; i<n; i++) {printf(“%d”,vec[i]);if(i!=n-1) printf(” “);}puts(“”);}return 0;}
人生没有彩排，只有现场直播，所以每一件事都要努力做得最好
