HDU 5195 DZY Loves Topological Sorting 拓扑排序

题目链接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5195

bc(中文):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=573&pid=1002

题解：

1、拓扑排序+贪心

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int n, m, k;

 struct Node {

     int v, flag;

     Node(int v,int flag=):v(v),flag(flag){}

     Node() { flag = ; }

 };

 vector<Node> head[maxn];

 int ind[maxn],done[maxn];

 void init() {

     for (int i = ; i < n; i++) {

         ind[i] = done[i]=;

         head[i].clear();

     }

 }

 int main() {

     while (scanf("%d%d%d", &n, &m, &k) ==  && n) {

         init();

         for (int i = ; i < m; i++) {

             int u, v;

             scanf("%d%d", &u, &v); u--, v--;

             ind[v]++;

             head[u].push_back(Node(v,));

         }

         priority_queue<int> pq;

         //删边

         for (int i = n - ; i >= ; i--) {

             if (k >= ind[i]) {

                 //将i的父亲ui中，满足ui<i，即边（ui,i）删了，这里要注意，对于边（ui,i),ui>i的边，根本不用删

                 k -= ind[i];

                 pq.push(i);

                 for (int j = ; j < head[i].size(); j++) {

                     Node &nd = head[i][j];

                     if (i > nd.v) {

                         //把边（i,v）删了，拓扑排序的时候不能再走这条边了

                         nd.flag = ;

                         ind[nd.v]--;

                     }

                 }

             }

         }

         vector<int> ans;

         //拓扑排序

         while (!pq.empty()) {

             int u = pq.top(); pq.pop();

             if (done[u]) continue;

             ans.push_back(u);

             done[u] = ;

             for (int i = ; i < head[u].size(); i++) {

                 Node& nd = head[u][i];

                 if (done[nd.v]||nd.flag) continue;

                 ind[nd.v]--;

                 if (ind[nd.v] == ) pq.push(nd.v);

             }

         }

         printf("%d", ans[]+);

         for (int i = ; i < ans.size(); i++) printf(" %d", ans[i]+);

         printf("\n");

     }

     return ;

 }

 /*

 5 3 1

 4 3

 1 3

 3 2

 5 3 0

 4 3

 1 3

 3 2

 */

2、线段树+贪心

对于节点i，入度为ind[i]，则可以这样贪心：对于1<=i<=n，求最大的i使得ind[i]<=k，我们可以把入度数组做成线段树，维护最小入度，二分查找，优先搜右边（右边的i会更大），找到以后，吧对于的子节点vj的入度减1，k-=ind[i]。这样一直做n次就能得到答案。

 #include<iostream>

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 #define lson (o<<1)

 #define rson ((o<<1)+1)

 #define M (l+(r-l)/2)

 using namespace std;

 const int maxn = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 int n, m, k;

 vector<int> head[maxn];

 int ind[maxn<<],minv[maxn<<];

 int _pos, _v;

 void update(int o, int l, int r) {

     if (l==r) {

         ind[o] += _v;

         minv[o] = ind[o];

     }

     else {

         if (_pos <= M) update(lson, l, M);

         else update(rson, M + , r);

         minv[o] = min(minv[lson], minv[rson]);

     }

 }

 void query(int o, int l, int r,int &res) {

     if (l == r) {

         if (ind[o] <= k) {

             k -= ind[o];

             res = l;

         }

     }

     else {

         //printf("lson:%d,rson:%d\n",minv[lson],minv[rson]);

         if (k >= minv[rson]) query(rson, M + , r,res);

         else if (k >= minv[lson]) query(lson, l, M,res);

     }

 }

 void init() {

     for (int i = ; i <= n; i++) head[i].clear();

     memset(ind, , sizeof(ind));

     memset(minv,,sizeof(minv));

 }

 int main() {

     while (scanf("%d%d%d", &n, &m, &k) ==  && n) {

         init();

         for (int i = ; i < m; i++) {

             int u, v;

             scanf("%d%d", &u, &v);

             head[u].push_back(v);

             _pos = v, _v = ;

             update(, , n);

         }

         //puts("after update");

         vector<int> ans;

         for (int i = ; i < n; i++) {

             int res;

             query(, , n, res);

             //puts("after first qurey!");

             //printf("res:%d\n", res);

             ans.push_back(res);

             for (int j = ; j < head[res].size(); j++) {

                 _pos = head[res][j], _v = -;

                 update(, , n);

                 //puts("after first upate");

             }

             _pos = res, _v = INF;

             update(, , n);

         }

         //puts("ans is zero");

         printf("%d", ans[]);

         for (int i = ; i < ans.size(); i++) printf(" %d", ans[i]);

         printf("\n");

     }

     return ;

 }