题解

18 条题解

  • 6
    @ 2017-05-15 13:30:39

    拓扑排序 (堆优化):

    #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    
    const int maxn = 100000;
    int _count[maxn], res[maxn];
    vector<int> G[maxn];
    priority_queue<int> que;
    
    int main() {
        int n, m;
        cin >> n >> m;
        while (m--) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            _count[u]++;
            G[v].push_back(u);
        }
        for (int i = 0; i < n; i++)
            if (_count[i] == 0)
                que.push(i);
        int tmp = n;
        while (!que.empty()) {
            int u = que.top();
            que.pop();
            res[u] = tmp--;
            for (int i = 0; i < G[u].size(); i++) {
                int v = G[u][i];
                _count[v]--;
                if (_count[v] == 0)
                    que.push(v);
            }
        }
        for (int i = 0; i < n; i++)
            cout << res[i] << " ";
        cout << endl;
        return 0;
    }
    
  • 4
    @ 2017-06-19 21:49:30

    建反边,每次取出入度为零的标号最大的节点分最大编号
    正向贪心样例即反例
    考虑最大编号,肯定分给最后的几个点,标号最大的,去掉这个点,再分再发最大编号

  • 3
    @ 2016-08-20 11:47:13

    正向贪心没过样例,仔细想想发现正向贪心可能导致前面的点的编号很大,所以就用逆向贪心,每次找入度为零且编号尽量大的点,把它放在拓扑序列的列首,并且删除所有指向这个点的有向边。
    代码实现如下,维护一个优先队列,只有当一个点的入度为零的时候才将它入队。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;

    const int maxn = 100000 + 10;
    const int maxm = 200000 + 10;

    int n, m;
    int clock;
    int cnt[maxn], id[maxn];
    vector<int> G[maxn];
    priority_queue<int> Q;

    int main () {
    cin >> n >> m;

    while (m--) {
    int u, v;
    scanf("%d%d", &u, &v); u--; v--;
    cnt[u]++;
    G[v].push_back(u);
    }

    for (int i = 0; i < n; i++) if (!cnt[i])
    Q.push(i);

    clock = n;
    while (!Q.empty()) {
    int u = Q.top(); Q.pop();
    id[u] = clock--;
    for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    cnt[v]--;
    if (cnt[v] == 0) Q.push(v);
    }
    }
    for (int i = 0; i < n; i++) printf("%d ", id[i]);
    return 0;
    }
    ```

  • 3
    @ 2015-02-01 13:11:38

    注意**逆拓扑序**的意思是
    1.翻转输入的所有边. 输入中若有u->v,则构图时是v->u.
    2.用优先队列挑字典序最大的一组.即,如果队列中有多个元素,选编号最大的那个.
    3.逆编号.第一个挑出来的城市赋值为n,第二个为n-1...最后一个为1.

  • 2
    @ 2017-02-03 18:58:22

    #include <bits/stdc++.h>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;

    const int N = 100000 + 5;

    int n, m, in[N], id[N];
    vector<int> mp[N];
    priority_queue<int> pq;

    int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
    int x, y; scanf("%d%d", &x, &y);
    in[x]++;
    mp[y].push_back(x);
    }
    int num = n;
    for (int i = 1; i <= n; i++) if (!in[i]) pq.push(i);
    while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    id[u] = num--;
    for (int i = 0; i < mp[u].size(); i++) {
    int v = mp[u][i];
    if (--in[v] == 0) pq.push(v);
    }
    }
    for (int i = 1; i <= n; i++) printf("%d ", id[i]);
    return 0;
    }

  • 1
    @ 2019-05-04 20:03:51

    是我的理解有什么偏差么?题解里都说每次选入度为0的,我越想越不对,自己写了个每次选出度为0的,最开始后三个点TimeOut,最后用了优先队列才过的。

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    int n,m;
    vector<int> edge[100001];
    int a[100001]={0};
    int ans[100001];
    priority_queue<int> que;
    
    int main()
    {
        cin>>n>>m;
        int i,j;
        int index;
        int from,to;
        for(i=0;i<m;i++)
        {
            cin>>from>>to;
            edge[to].push_back(from);
            a[from]++;
        }
        int acc=n;
        for(i=1;i<=n;i++)
        {
            if(a[i]==0)
            {
                que.push(i);
            }
        }
        while(!que.empty())
        {
            index=que.top();
            que.pop();
            ans[index]=acc;
            acc--;
            for(j=edge[index].size()-1;j>=0;j--)
            {
                i=edge[index][j];
                a[i]--;
                if(a[i]==0)
                {
                    que.push(i);
                }
            }
        }
        cout<<ans[1];
        for(i=2;i<=n;i++)
        {
            cout<<' '<<ans[i];
        }
        cout<<endl;
        return 0;
    }
    
  • 1
    @ 2018-05-27 15:27:22

    反向拓扑 + 堆优化
    //
    // main.cpp
    // 1790
    //
    // Created by Jack Zhang on 2018/5/27.
    // Copyright © 2018年 Jack Zhang. All rights reserved.
    //

    #include <iostream>
    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <cstring>
    using namespace std;
    priority_queue<int/*, vector<int>, greater<int> */> stk;
    const int maxn = 100010;
    int n,m, in[maxn], a[maxn], newname;
    vector <int> out[maxn];
    int main(int argc, const char * argv[]) {
    memset(in, 0, sizeof(in));
    scanf("%d%d", &n, &m);
    newname = n;
    for(int i=0;i<m;i++) {
    int x,y;
    scanf("%d%d", &x, &y);
    swap(x, y);
    int flag = true;
    for(int j=0;j<out[x].size();j++){
    if(out[x][j] == y){
    flag = false;
    break;
    }
    }
    if(flag){
    out[x].push_back(y);
    in[y]++;
    }
    }
    for(int i=1;i<=n;i++){
    if(in[i]==0) stk.push(i);
    }
    while(!stk.empty()){
    int p = stk.top();
    stk.pop();
    a[p]=newname--;
    for(int i=0;i<out[p].size();i++){
    int to = out[p][i];
    in[to]--;
    if(in[to]==0) stk.push(to);
    }
    }
    for(int i=1;i<=n;i++){
    cout<<a[i];
    if(i!=n)cout<<" ";
    }
    return 0;
    }

  • 0
    @ 2016-11-13 19:45:10

    建反边,堆优化
    type
    ab=^node;
    node=record
    ed:longint;
    nx:ab;
    end;

    var
    i,n,m,l,z,x,y:longint;
    ph:array[0..100000] of ab;
    heap,a,d:array[0..100000] of longint;

    procedure swap(var x,y:longint);
    var p:longint;
    begin
    p:=x;x:=y;y:=p;
    end;

    procedure init(y,x:longint);
    var i:ab;
    begin
    i:=ph[y];
    new(ph[y]);
    ph[y]^.ed:=x;
    ph[y]^.nx:=i;
    end;

    function get:longint;
    var i,j:longint;
    begin
    get:=heap[1];
    heap[1]:=heap[l];
    dec(l);
    i:=1;
    while i shl 1<=l do
    begin
    j:=i shl 1;
    if (j<l)and(heap[j]<heap[j+1]) then inc(j);
    if heap[i]<heap[j] then
    begin
    swap(heap[i],heap[j]);
    i:=j;
    end
    else
    break;
    end;
    end;

    procedure put(x:longint);
    var i,j:longint;
    begin
    inc(l);
    heap[l]:=x;
    i:=l;
    while i>1 do
    begin
    j:=i shr 1;
    if heap[j]<heap[i] then
    begin
    swap(heap[i],heap[j]);
    i:=j;
    end
    else
    break;
    end;
    end;

    procedure doit;
    var i,j:longint;
    p:ab;
    begin
    l:=0;
    for i:=1 to n do
    if d[i]=0 then
    begin
    put(i);
    d[i]:=maxlongint;
    end;
    while l>0 do
    begin
    i:=get;
    p:=ph[i];
    inc(z);
    a[i]:=z;
    while p<>nil do
    begin
    j:=p^.ed;
    dec(d[j]);
    if d[j]=0 then
    begin
    put(j);
    d[j]:=maxlongint;
    end;
    p:=p^.nx;
    end;
    end;
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(x,y);
    inc(d[x]);
    init(y,x);
    end;
    doit;
    for i:=1 to n do
    write(n-a[i]+1,' ');
    end.

  • 0
    @ 2016-08-28 15:29:51

    想了半天没想到逆向拓扑贪心。。。。

  • 0
    @ 2016-08-28 10:54:56

    我已经发现vijos的cin和cout很神奇了。就算关闭流同步依然慢成狗。换成scanf瞬间降一半。
    思路楼下说过了,这里给出29行代码
    c++
    #include <cstdio>
    #include <vector>
    #include <queue>
    using namespace std;
    int main()
    {
    int n,m,x,y,i,count;
    scanf("%d%d",&n,&m);count=n;
    vector<vector<int> >list(n+1);vector<int> in(n+1),a(n+1);priority_queue<int> que;
    for(i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    list[y].push_back(x);in[x]++;
    }
    for(i=1;i<=n;i++)if(!in[i])que.push(i);
    while(!que.empty())
    {
    int load=que.top();
    que.pop();a[load]=count--;
    for(vector<int>::iterator ite=list[load].begin();ite!=list[load].end();ite++)
    if(!a[*ite])
    {
    in[*ite]--;
    if(!in[*ite])que.push(*ite);
    }
    }
    for(i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
    }

  • 0
    @ 2015-06-21 13:17:58

    逆拓扑排序+优先队列也能写

  • 0
    @ 2014-11-29 13:56:42

    我在我的博客里 写了这个算法的证明 感兴趣的朋友可以 参考一下 欢迎指出错误
    http://www.cnblogs.com/vb4896/p/4083650.html

  • 0
    @ 2014-06-15 17:18:15

    拓扑排序+堆

  • 0
    @ 2014-02-27 18:26:04

    逆拓扑排序+堆
    逆拓扑排序,每次取出入度为零的节点时,要取出标号最大的节点。
    找标号最大的节点可以用堆进行优化
    代码如下:

    type
    node=^rec1;
    rec1=record data:longint;next:node; end;
    rec2=record ru:longint;link:node; end;
    var
    i,n,m,l,z,x,y:longint;p:node;
    g:array[0..100000] of rec2;
    heap,a:array[0..100000] of longint;

    procedure swap(var x,y:longint);
    var p:longint;
    begin
    p:=x;x:=y;y:=p;
    end;

    procedure swim;
    var i,j:longint;
    begin
    i:=1;
    while i shl 1<=l do
    begin
    j:=i shl 1;
    if (j<l)and(heap[j]<heap[j+1]) then inc(j);
    if heap[i]<heap[j] then
    begin
    swap(heap[i],heap[j]);i:=j;
    end
    else break;
    end;
    end;

    procedure add(x:longint);
    var i,j:longint;
    begin
    inc(l);heap[l]:=x;i:=l;
    while i>1 do
    begin
    j:=i shr 1;
    if heap[j]<heap[i] then
    begin
    swap(heap[i],heap[j]);i:=j;
    end
    else break;
    end;
    end;

    procedure toposort;
    var i,j:longint;p:node;
    begin
    l:=0;
    for i:=1 to n do
    if g[i].ru=0 then
    begin
    add(i);g[i].ru:=maxlongint;
    end;
    while l>0 do
    begin
    i:=heap[1];heap[1]:=heap[l];
    dec(l);swim;p:=g[i].link;
    inc(z);a[i]:=z;
    while p<>nil do
    begin
    j:=p^.data;dec(g[j].ru);
    if g[j].ru=0 then
    begin
    add(j);g[j].ru:=maxlongint;
    end;
    p:=p^.next;
    end;
    end;
    end;

    begin
    readln(n,m);
    for i:=1 to n do
    begin
    g[i].ru:=0;g[i].link:=nil;
    end;
    for i:=1 to m do
    begin
    readln(x,y);inc(g[x].ru);new(p);
    p^.data:=x;p^.next:=g[y].link;g[y].link:=p;
    end;
    toposort;
    for i:=1 to n do write(n-a[i]+1,' ');
    end.

  • 0
    @ 2013-11-04 07:48:12

    这道题做了好长时间 一开始 证明了正向的贪心不对后 虽然也想到了 反向的贪心 但始终说服不了自己 于是写了一个 dfs计算每个点可以走到的最小点 以及达到这个最小点的 path 然后写了个三关键字的堆 好 然后标号 。。。。。这样是错的 以路径为一个关键字的贪心不太正确

    然后 听了神牛的讲评

    反向的严格证明 不知道
    但是 正向贪心 显然会错误 但是 反向的话 出度为零 的最大点为最后一个丝毫不违反 规则 并且可以说 很好的迎合了“国王”的规则 所以 。。。就这样 (语言表达能力好差 )

    • @ 2014-10-15 16:38:38

      居然有人跟我的想法一样= =
      只比较最小点的确是错的 稍微说明(证明?)一下就是:两条路径所能走到的最小点可能是一样的,此时就要比较次小点,次小点一样的时候又要继续比较两条路径上第三小的点……

  • 0
    @ 2013-08-03 14:57:57

    为什么要反过来???

  • 0
    @ 2013-07-23 14:04:43

    过了七个点,最后三个点过不了,代码如下,不知道大家有没有好的方法,过掉最后三个大数据的点

    program vijos1790;
    type
    tnode=^node;
    node=record
    p:longint;
    next:tnode;
    end;
    var
    tosort,tosort2,after:array[1..100010] of longint;
    f:array[1..100010] of tnode;
    i,j,n,m,u,v,k:longint;
    t:tnode;
    function find(u,v:longint):boolean;
    var temp:tnode;
    begin
    temp:=f[u];
    while temp<>nil do
    begin
    if temp^.p=v then
    exit(true);
    temp:=temp^.next;
    end;
    exit(false);
    end;

    begin
    readln(n,m);
    fillchar(after,sizeof(after),0);

    for i:=1 to m do
    begin
    readln(u,v);
    if ( not find(u,v)) then
    begin
    inc(after[u]);
    new(t);
    t^.p:=v;
    t^.next:=f[u];
    f[u]:=t;
    end;

    end;

    i:=n;
    while i>0 do
    begin
    j:=n;
    while after[j]<>0 do dec(j);
    after[j]:=-1;
    for k:=1 to n do
    if find(k,j) then
    begin

    dec(after[k]);
    end;

    tosort[i]:=j;
    dec(i);
    end;
    for i:=1 to n do
    tosort2[tosort[i]]:=i;
    for i:=1 to n-1 do
    write(tosort2[i],' ');
    writeln(tosort2[n]);

    end.

  • -2
    @ 2018-03-07 20:15:05

    缩缩缩

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    const int MAXN = 100000 + 10;
    vector<int> g[MAXN];
    priority_queue<int> q;
    int n, cnt[MAXN], u, v, m, tick, res[MAXN];
    
    int main(){
        cin.sync_with_stdio(false); cout.sync_with_stdio(false);
        cin >> n >> m;
        tick = n;
        for (int i = 1; i <= m; i++){
            cin >> u >> v;
            g[v].push_back(u);
            cnt[u]++;
        }
        for (int i = 1; i <= n; i++) if (!cnt[i]) q.push(i);
        while (!q.empty()){
            int cur = q.top(); q.pop();
            res[cur] = tick--;
            for (int i = 0; i < g[cur].size(); i++) if (!--cnt[g[cur][i]]) q.push(g[cur][i]);
        }
        for (int i = 1; i <= n; i++) cout << res[i] << " ";
        cout << endl;
        return 0;
    }
    
    
  • 1

信息

ID
1790
难度
5
分类
图结构 | 拓扑排序数据结构 点击显示
标签
(无)
递交数
978
已通过
301
通过率
31%
被复制
9
上传者