拓扑排序·DAG

Hua生 · 2022-06-15 11:50:21 · 个人记录

UVA10305 给任务排序

赵老师规范的拓扑排序模板：（2022.11.15修改）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 110
int n,m,head[N],ind[N],toplist[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[N*N];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
bool toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]) toplist[rear++]=i;
    }
    while(front<rear){
        x=toplist[front++];
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
    if(rear<n) return 0;
    else return 1;
}
int main(){
    while(1){
        memset(head,-1,sizeof(head));tot=-1;
        memset(toplist,0,sizeof(toplist));
        memset(ind,0,sizeof(ind));
        scanf("%d%d",&n,&m);
        if(!n&&!m) break;
        int i,x,y;
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x,y);
            ind[y]++;
        }
        toposort();
        for(i=0;i<n;i++) printf("%d ",toplist[i]);
        printf("\n");
    }
    return 0;
}

只要一个图存在拓扑序列，那么它可能存在多种拓扑序。

有向无环图又称作 DAG 图。

判断没有拓扑序时检验队列里的元素数量。

P1137 旅行计划

下面开始拓扑排序的应用。

设 f[i] 表示终点为 i 的点的方案数。在拓扑排序的初始化中，起点入队时 f[i]=1。转移过程中，f[i]=max(f[i],f[x]+1)，因为最后更新的答案未必最大（防止其他题目因此出错）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 100100
#define M 200100
int n,m,head[N],ind[N],toplist[N],f[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[M];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
void toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            toplist[rear++]=i;
            f[i]=1;
        }
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            f[edge[i].v]=max(f[edge[i].v],f[x]+1);
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    int i,x,y;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        ind[y]++;
    }
    toposort();
    for(i=1;i<=n;i++) printf("%d\n",f[i]);
    return 0;
}

P1113 杂务

刷表法：与上一题类似。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 10100
#define M 100*N
int n,head[N],a[N],ind[N],toplist[N],f[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[M];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
void toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            toplist[rear++]=i;
            f[i]=a[i];
        }
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<" "<<a[x]<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            f[edge[i].v]=max(f[edge[i].v],f[x]+a[edge[i].v]);
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    int i,x,y,z,ans=0;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z);
        a[x]=y;
        while(z){
            add(z,x);
            //cout<<"//B"<<z<<" "<<x<<endl;
            ind[x]++;
            scanf("%d",&z);
        }
    }
    toposort();
    for(i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

填表法：记忆化搜索，其他类似。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 10100
#define M 100*N
int n,head[N],a[N],f[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[M];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
void dfs(int x){
    if(f[x]) return;
    for(int i=head[x];~i;i=edge[i].nxt){
        dfs(edge[i].v);
        f[x]=max(f[x],f[edge[i].v]);
    }
    f[x]=f[x]+a[x];
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    int i,x,y,z,ans=0;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z);
        a[x]=y;
        while(z){
            add(z,x);
            scanf("%d",&z);
        }
    }
    for(i=1;i<=n;i++){
        dfs(i);
        ans=max(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}

T118124 奖金

最先确定的是得到最低工资的员工，因此反向建边。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 10100
#define M 20100
int n,m,head[N],ind[N],toplist[N],f[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[M];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
bool toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            toplist[rear++]=i;
            f[i]=100;
        }
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            f[edge[i].v]=max(f[edge[i].v],f[x]+1);
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
    if(rear<n) return 0;
    else return 1;
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    int i,x,y,ans=0;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(y,x);
        ind[x]++;
    }
    if(toposort()){
        for(i=1;i<=n;i++) ans+=f[i];
        printf("%d",ans);
    }
    else printf("-1");
    return 0;
}

P4017 最大食物链计数

题目描述不清晰，求食物链的数量（看不懂的建议重修初二生物）。

本题还需要一个 oud[i] 记录出度，如果出度为0，再计算答案，保证是最高级消费者。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 5100
#define M 500100
#define P 80112002
int n,m,head[N],ind[N],oud[N],toplist[N],f[N],tot=-1;
struct node{
    int u,v,nxt;
}edge[M];
void add(int x,int y){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
void toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            toplist[rear++]=i;
            f[i]=1;
        }
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            f[edge[i].v]=(f[edge[i].v]+f[x])%P;
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    int i,x,y,ans=0;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(y,x);
        ind[x]++;
        oud[y]++;
    }
    toposort();
    for(i=1;i<=n;i++){
        if(!oud[i]) ans=(ans+f[i])%P;
    }
    printf("%d",ans);
    return 0;
}

P1807 最长路

看似是最简单的一道题，实际上是问题最大的一道题。

边权 -10^5<w<10^5，初始值最好较小。

可能1结点入度不为0，但我没处理，还 AC 了？

对于其他的支路，可以删边，但不好操作。

判无解时看 f[n] 取值，如果是初始值则无解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 2000
#define M 50100
int n,m,head[N],ind[N],toplist[N],tot=-1;
long long f[N];
struct node{
    int u,v,w,nxt;
}edge[M];
void add(int x,int y,int z){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].w=z;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
bool toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            toplist[rear++]=i;
            if(i==1) f[i]=0;
        }
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            f[edge[i].v]=max(f[edge[i].v],f[x]+edge[i].w);
            if(!ind[edge[i].v]) toplist[rear++]=edge[i].v;
        }
    }
    if(rear<n) return 0;
    else return 1;
}
int main(){
    memset(head,-1,sizeof(head));
    memset(f,0xc0,sizeof(f));
    scanf("%d%d",&n,&m);
    int i,x,y,z;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        ind[y]++;
    }
    if(toposort()&&f[n]>(long long)0xc0c0c0c0c0c0c0c0) printf("%lld",f[n]);
    else printf("-1");
    return 0;
}
//5 4 1 3 1 2 3 100 3 4 -7 4 5 1

P1038 神经网络

输入的描述不清晰，对于每个神经元，第一个数 c[i] 表示神经元的状态，第二个数 u[i] 表示阈值。

递推式有点复杂，但按照那个式子算即可。注意在所有入度处理完后再 -u[i]。

需要 oud[i] 记录出度，验证是不是输出层神经元。

一遍过。（我也很意外）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 110
#define M N*N
int n,m,head[N],u[N],ind[N],oud[N],toplist[N],tot=-1;
long long f[N];
struct node{
    int u,v,w,nxt;
}edge[M];
void add(int x,int y,int z){
    edge[++tot].u=x;
    edge[tot].v=y;
    edge[tot].w=z;
    edge[tot].nxt=head[x];
    head[x]=tot;
}
bool toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]) toplist[rear++]=i;
    }
    while(front<rear){
        x=toplist[front++];
        //cout<<"//A"<<x<<endl;
        for(i=head[x];~i;i=edge[i].nxt){
            ind[edge[i].v]--;
            if(f[x]>0) f[edge[i].v]+=f[x]*edge[i].w;
            if(!ind[edge[i].v]){
                f[edge[i].v]-=u[edge[i].v];
                toplist[rear++]=edge[i].v;
            }
        }
    }
    if(rear<n) return 0;
    else return 1;
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    int i,x,y,z;
    bool check=1;
    for(i=1;i<=n;i++) scanf("%lld%d",&f[i],&u[i]);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        ind[y]++;oud[x]++;
    }
    toposort();
    for(i=1;i<=n;i++){
        if(!oud[i]&&f[i]>0){
            check=0;
            printf("%d %lld\n",i,f[i]);
        }
    }
    if(check) printf("NULL");
    return 0;
}

P1983 车站分级

记得之前见过这个题，试图解决，不会拓扑排序，失败……

将区间内不停的站（低级站）与停车的站（高级站）连边。从小到大计算层次。由于会有大量重边，数据范围 1≤n,m≤1000，可以使用邻接矩阵解决。注意计算入度时不要重复！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1010
int n,m,ind[N],q[N],f[N];
bool a[N][N],vis[N];
void toposort(){
    int i,x,front=0,rear=0;
    for(i=1;i<=n;i++){
        if(!ind[i]){
            q[rear++]=i;
            f[i]=1;
        }
    }
    while(front<rear){
        x=q[front++];
        //cout<<"//A"<<x<<" "<<f[x]<<endl;
        for(i=1;i<=n;i++){
            if(a[x][i]){
                ind[i]--;
                //cout<<"//D"<<x<<" "<<i<<" "<<ind[i]<<endl;
                f[i]=max(f[i],f[x]+1);
                if(!ind[i]) q[rear++]=i;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int i,j,h,x,y,s,t,ans=0;
    for(i=1;i<=m;i++){
        scanf("%d",&x);
        memset(vis,0,sizeof(vis));
        for(j=1;j<=x;j++){
            scanf("%d",&y);
            if(j==1) s=y;
            if(j==x) t=y;
            vis[y]=1;
        }
        for(j=s;j<=t;j++){
            for(h=j+1;h<=t;h++){
                if(vis[j]&&!vis[h]){
                    if(!a[h][j]) ind[j]++;
                    a[h][j]=1;
                    //cout<<"//B"<<h<<" "<<j<<endl;
                }
                if(vis[h]&&!vis[j]){
                    if(!a[j][h]) ind[h]++;
                    a[j][h]=1;
                    //cout<<"//C"<<j<<" "<<h<<endl;
                }
            }
        }
    }
    toposort();
    for(i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

UVA437 巴比伦塔

一点思路也没有。

今天大课间跑操取消，Qyc 来给我们讲欧拉路。讲的方法比较复杂，没有举具体例子，很多同学迷迷糊糊。终于明白为什么 Qyc 的语文差了。又突然回想起初三上开学前的那个集训，我没听明白一道题。

（2022年6月15日上午）

（2022年11月15日修改）