参考:洛谷日报 快速入手拓扑排序

HDU 1285 确定比赛名次

拓扑排序模板题,唯一不同的是要求编号小的在前,把队列改成优先队列就行了。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int dp[N];
int d[N];
vector<int>g[N];
vector<int>ans;
void topo() // 拓扑排序
{
    priority_queue<int,vector<int>,greater<int> >q; // 编号小的在前
    while(!q.empty())q.pop();
    ans.clear();
    for(int i=1;i<=n;i++)
        if(!d[i])q.push(i);
    while(!q.empty())
    {
        int u=q.top();q.pop();
        ans.push_back(u);
        int sz=g[u].size();
        for(int i=0;i<sz;i++)
        {
            int v=g[u][i];
            d[v]--;
            if(d[v]==0)q.push(v);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m) 
    {
        for(int i=1;i<=n;i++)
            g[i].clear();
        memset(d,0,sizeof(d));
        int x,y;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y; // 不去重边也没事,可以自己模拟一下
            g[x].push_back(y);
            d[y]++;
        }
        topo();
        for(int i=0;i<n;i++)
            i==n-1?printf("%d\n",ans[i]):printf("%d ",ans[i]);
    }
    return 0;
}
/*
5 5
1 3
1 5
3 4
5 2
2 4
ans: 1 3 5 2 4
*/

洛谷 P1807 最长路

题目明确说明是有向无环图,所以可以用拓扑排序求最长路(有环图求最长路只能用SPFA算法!)

#include <bits/stdc++.h>
using namespace std;
const int N=1510,M=5e4+10;
queue<int>q;
int n,m,x,y,z,cnt,d[N],dp[N],vis[N],head[N];
//dp[i]表示从点1出发到达i点时的权值(最长路),d[i]表示i点的入度
struct edge
{
    int w,to,next;
}e[M];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void topo_sort()//拓扑排序
{
    for(int i=1;i<=n;i++)//入度为0的点全部都要入队,不能只将点1入队
        if(d[i]==0)q.push(i);
    vis[1]=1;//vis[i]=1表示i点是以点1为起点搜索到的点,否则i点不是以点1为起点搜索到的点
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(vis[u]==1)
            {
                dp[v]=max(dp[v],dp[u]+e[i].w);
                vis[v]=1;
            }
            d[v]--;//搜到v点了,把v点入度减一(就是除去现在搜到的边e[i])
            if(d[v]==0)q.push(v);//v点入度为0则入队
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        d[y]++;//统计入度
    }
    dp[n]=-1;
    topo_sort();
    printf("%d\n",dp[n]);
    return 0;
}

本题还可以用SPFA的思想,只要把SPFA模板中的一个小于号改成大于号就行了。
(SPFA可以求最长路,但是Dijkstra不可以!)

#include <bits/stdc++.h>
using namespace std;
const int N=1510,M=5e4+10;
int n,m,x,y,z,cnt,dis[N],vis[N],head[N];
struct edge
{
    int w,to,next;
}e[M];//定义边的三个信息,w表示边权,to表示边的终点,next表示上一条边
void add(int x,int y,int z)//链式前向星存边
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];//next表示以x为起点的上一条边的编号
    head[x]=cnt++;//head[x]表示以x为起点的最后一条边的编号
}
queue<int>q;
void spfa()
{
    q.push(1);//起点入队
    dis[1]=0;//起点到自身距离为0
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(int i=head[u];i!=-1;i=e[i].next)//遍历以u为起点的所有边
        {
            int v=e[i].to;
            if(dis[u]+e[i].w>dis[v])//只要把小于号改成大于号就行了
            {
                dis[v]=dis[u]+e[i].w;
                if(vis[v]==0)
                    q.push(v),vis[v]=1;//入队标记
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    memset(dis,-1,sizeof(dis));
    spfa();
    printf("%d\n",dis[n]);
    return 0;
}

洛谷 P4017 最大食物链计数

#include <bits/stdc++.h>
using namespace std;
const int N=5010,M=5e5+10,mod=80112002;
queue<int>q;
int n,m,x,y,cnt,ans,d[N],dp[N],vis[N],head[N];
//dp[i]表示到达i点时的权值(食物链条数),d[i]表示i点的入度
struct edge
{
    int to,next;
}e[M];
void add(int x,int y)
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void topo_sort()//拓扑排序
{
    for(int i=1;i<=n;i++)
        if(d[i]==0)q.push(i),dp[i]=1;//入度为0则入队,初始化入度为0的点的权值为1
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            dp[v]=(dp[v]+dp[u])%mod;
            d[v]--;//搜到v点了,把v点入度减一(就是除去现在搜到的边e[i])
            if(d[v]==0)q.push(v);//v点入度为0则入队
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y);
        d[y]++;//统计入度
        vis[x]=1;//x被作为起点(被捕食者)标记
    }
    topo_sort();
    for(int i=1;i<=n;i++)
        if(vis[i]==0)ans=(ans+dp[i])%mod;
        //统计没有被作为起点(每条食物链最顶端)的点的权值和
    printf("%d\n",ans);
    return 0;
}