拓扑排序-上

拓扑排序例题：

模板题1：P4017 传送

题意：

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入：

第一行，两个正整数 $n,m$ ，表示生物种类 $n$ 和吃与被吃的关系数 $m$ 。

接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出：

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

思路：

记录下所有入度数为0的节点，将他们的初始状态 $dp[i]$ 定义为1.之后对于 $x$ 的所有后继节点 $y$

定义出度数为0的节点个数为m。

状态转移方程为： $dp[y]=max(dp[x]+1,dp[y])$ 输出 $\sum_{i}dp[i],i\in m$ 。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
#define ll long long
#define mod 80112002
ll n,m;
vector <int> mp[MAXN];
int indgr[MAXN];
int outdgr[MAXN];
ll dp[MAXN];
ll ans=0;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u].emplace_back(v);
        indgr[v]++;
        outdgr[u]++;
    }
    queue <int> q;
    for(int i=1;i<=n;i++)
    {
        if(indgr[i]==0)
        {
            dp[i]=1;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(auto it:mp[now])
        {
            dp[it]=(dp[it]+dp[now])%mod;
            indgr[it]--;
            if(indgr[it]==0)
            {
                if(outdgr[it]==0) ans=(ans+dp[it])%mod;
                q.push(it);
            }
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

模板题2：求最长路传送

设 $G$ 为有 $n$ 个顶点的带权有向无环图， $G$ 中各顶点的编号为 $1$ 到 $n$ ，请设计算法，计算图 $G$ 中 $1,n$ 间的最长路径。

分析：

首先这是一个有向无环图，因为如果有环不存在最长路。那么很明显就可以用拓扑遍历进行松弛操作，当 $dis[next]<dis[now]+edge[i].val$ 进行更新。注意将INF赋值为负无穷。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 50005
int head[MAXN];int tot;
struct node
{
    int to,next,val;
}edge[MAXN];
void add_edge(int from,int to,int val)
{
    edge[++tot].to=to;edge[tot].val=val;edge[tot].next=head[from];head[from]=tot;
}
#define INF -114514114514
int indgr[MAXN];ll dp[MAXN];//1到i的最长路
ll n,m;

void topp()
{
    queue <int> q;
    for(int i=1;i<=n;i++)
    {
        if(indgr[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int next=edge[i].to;
            int val=edge[i].val;
            if(dp[now]+val>dp[next])
            {
                dp[next]=dp[now]+val;
            }
            indgr[next]--;
            if(indgr[next]==0) q.push(next);
        }
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
        indgr[v]++;
    }
    for(int i=2;i<=n;i++) dp[i]=INF;
    topp();
    if(dp[n]==INF) cout<<-1<<endl;
    else cout<<dp[n]<<endl;
}


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

郁闷的记者（对于拓扑序的理解）传送

你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。

以下是给你的一些信息：

(1)没有平局；

(2)不同的球队排名不能相同；

(3)对于所有满足l≤a<b≤n，第a名的球队一定可以打败第b名的球队。

给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。

分析：

什么叫存在令一种排名方法满足比赛结果呢？是不是可以理解为会有并列排名的选手出现。比如1号选手和3号选手都能打败2号选手，但也都不能打败4号选手。将这种抽象为图即是这样的结果

可以发现，转化为图后，1号和3号在拓扑排序中就意味着同一级别，换句话说就是能在 一次遍历中同时入队 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 5005
ll n,m;
//保证没有自环，同一级别的入队次数只能为1
vector <ll> mp[MAXN];
ll indgr[MAXN];
int flag=0;
vector <int> ans;
void build()
{
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u].emplace_back(v);
        indgr[v]++;
    }
}

void topp()
{
    queue <int> q;
    int cnt=0;//记录同一级别的人的个数，大于1就有多种排名情况
    for(int i=1;i<=n;i++)
    {
        if(indgr[i]==0)
        {
            cnt++;
            q.push(i);
            ans.emplace_back(i);
        }
    }
    if(cnt>1) flag=1;
    while(!q.empty())
    {
        cnt=0;
        int now=q.front();q.pop();
        for(auto it:mp[now])
        {
            indgr[it]--;
            if(indgr[it]==0)
            {
                cnt++;
                ans.emplace_back(it);
                q.push(it);
            }
        }
        if(cnt>1) flag=1;
    }
}

void output()
{
    for(auto x:ans) cout<<x<<endl;
    cout<<flag;
}

void solve()
{
    cin>>n>>m;
    build();
    topp();
    output();
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

摄像头（对入度的理解）传送

食品店里有 $n$ 个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。

为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。

现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。

输入：

第 $1$ 行，一个整数 $n$ ，表示摄像头的个数。

第 $2$ 到 $n+1$ 行是摄像头的信息，包括：摄像头的位置 $x$ ，以及这个摄像头可以监视到的位置数 $m$ ，之后 $m$ 个数 $y$ 是此摄像头可以监视到的位置。(砸了这些摄像头之后自然这些位置就监视不到了)

分析：

根据这些摄像机组成的监视网络构建一张有向无环图，遍历它。遍历完成后，那些入度数为 $0$ 的摄像头位置就可以砸掉了，因为能监控这个摄像头的所有摄像头（可以没有任何摄像头）也可以被砸掉。这题坑的地方就是有的地方不一定有摄像头，得开个 $visit$ 记录一下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 505
vector <int> mp[MAXN];
int indgr[MAXN];//有些入度大于0的地方可能没有摄像头
int visit[MAXN];
ll n,m;

void build()
{
    for(int i=1;i<=n;i++)
    {
        int id;
        cin>>id>>m;
        visit[id]=1;
        while(m--)
        {
            int to;
            cin>>to;
            mp[id].emplace_back(to);
            indgr[to]++;
        }
    }
}

void topp()
{
    int del=0;
    queue <int> q;
    for(int i=1;i<=n;i++) if(indgr[i]==0&&visit[i]==1) 
    {
        q.push(i);
        del++;
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(auto it:mp[now])
        {
            indgr[it]--;
            if(indgr[it]==0&&visit[it]==1) 
            {
                q.push(it);
                del++;
            }
        }
    }
    if(del==n) cout<<"YES"<<endl;
    else cout<<n-del<<endl;
}

void solve()
{
    cin>>n;
    build();
    topp();
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

Timeline G （建图的哲学）传送

Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$ ，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。

现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：

第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
所有的记忆都得到满足；

样例1：

分析：

她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$ ，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。对于题目给出的这个条件，我们可以很容易的建图，像这样

但另外一个条件我们怎么利用呢？想象一下，是不是可以新建一个超级源点 $0$ ，这个点的入度为0，和每个其他的节点都有一条出边，这样就可以完成图的构建，进而进行拓扑排序了。

转移方程为 $dp[next]=max(dp[now]+edge[i].val,dp[next])$

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
int indgr[MAXN<<1];int head[MAXN<<1]; ll tim[MAXN<<1];
struct node
{
    int to,next,val;

}edge[MAXN<<1];
int cnt=0;
void add_edge(int from,int to,int val)
{
    edge[++cnt].val=val;edge[cnt].to=to;edge[cnt].next=head[from];head[from]=cnt;
}
ll n,m,k;

void solve()
{
    cin>>n>>k>>m;
    for(int i=0;i<=n;i++) 
    {
        head[i]=-1;
        tim[i]=-1;
    }
    tim[0]=0;
    for(int i=1;i<=n;i++)
    {
        int temp;
        cin>>temp;
        add_edge(0,i,temp);
        indgr[i]++;
    }
    for(int i=1;i<=m;i++)
    {
        int to,from,val;
        cin>>from>>to>>val;
        add_edge(from,to,val);
        indgr[to]++;
    }
    queue <int> q;
    q.push(0);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i!=-1;i=edge[i].next)
        {
            int val=edge[i].val;
            int j=edge[i].to;
            tim[j]=max(tim[j],tim[now]+val);
            indgr[j]--;
            if(indgr[j]==0) q.push(j);
        }
    }
    for(int i=1;i<=n;i++) cout<<tim[i]<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

菜肴制作（建图的智慧）传送

知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 $n$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 $n$ 的顺序编号，预估质量最高的菜肴编号为 $1$ 。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 $m$ 条形如 $i$ 号菜肴必须先于 $j$ 号菜肴制作的限制，我们将这样的限制简写为 $(i,j)$ 。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：

例 1：共 $4$ 道菜肴，两条限制 $(3,1)$ 、 $(4,1)$ ，那么制作顺序是 $3,4,1,2$ 。

例 2：共 $5$ 道菜肴，两条限制 $(5,2)$ 、 $(4,3)$ ，那么制作顺序是 $1,5,2,4,3$ 。

分析：

很自然的想到按照字典序进行拓扑排序，但是仔细想想就是错的，比如 $(2,4),(3,1)$ 这组限制条件。题目要求的最优解为 $3,1,2,4$ ，但是做出来确是 $2,3,1,4$ 的效果。

继续考虑，如果说要把字典序小的先安排是不是就相当于把字典序大的尽可能往后安排呢。

这样我们就可以构造一个反图，每次让最大的入队（用大顶堆实现），这样就能保证小的尽可能晚的入队，满足了题意，到最后反着输出这个序列就行了。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
ll n,m;
int head[MAXN];int cnt=0;
int indgr[MAXN];
vector <int> ans;
struct node
{
    int to,next;
}edge[MAXN];
void add_edge(int from,int to)
{
    edge[++cnt].to=to;edge[cnt].next=head[from];head[from]=cnt;
}
void init()
{
    cnt=0;
    ans.clear();
    for(int i=1;i<=n;i++) 
    {
        indgr[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        head[i]=0;
        edge[i].to=0;edge[i].next=0;
    }
}
void build()
{
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add_edge(v,u);
        indgr[u]++;
    }
}
void topp()
{
    priority_queue <int> q;
    for(int i=n;i>=1;i--)
    {
        if(indgr[i]==0) 
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.top();q.pop();
        ans.emplace_back(now);
        for(int i=head[now];i;i=edge[i].next)
        {
            int j=edge[i].to;
            indgr[j]--;
            if(indgr[j]==0)
            {
                //ans.emplace_back(j);
                q.push(j);
            }
        }
    }
}
void output()
{
    if(ans.size()!=n) cout<<"Impossible!";
    else 
    {
       for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
    }
    cout<<endl;
}
void solve()
{
    cin>>n>>m;
    init();
    build();
    topp();
    output();
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

拓扑排序例题：

模板题1：P4017 传送

模板题2：求最长路 传送

郁闷的记者 （对于拓扑序的理解）传送

摄像头 （对入度的理解） 传送

Timeline G （建图的哲学） 传送

菜肴制作（建图的智慧）传送

模板题2：求最长路传送

郁闷的记者（对于拓扑序的理解）传送

摄像头（对入度的理解）传送

Timeline G （建图的哲学）传送