拓扑排序三题（菜肴制作杂物最大食物链计数）

目录

一、【HNOI]菜肴制作

二、洛谷1113杂物

代码一：

代码二：

三、最大食物链计数【洛谷4017】

DAG:有向无环图

图的建立很重要

一、【HNOI]菜肴制作

传送门1

思路&技巧：倒过来看，因为要让尽可能小的数字先选，也就是大的后选，整个图倒着建，先选最大的、入度为0的点，输出时再倒过来。

#include<iostream>#include<queue>#include<cstring>using namespace std;const int M=1e5+6;int ct,T,n,m,head[M],inc[M],ans[M];//inc[]入度 struct ED{int t,next;}e[M];void addedge(int u,int v){e[++ct].t=v;e[ct].next=head[u];head[u]=ct;}priority_queue<int> q;bool tuopu(){//while(!q.empty())q.pop();//可以不要，不会出现不为空的情况 for(int i=1;i<=n;i++)if(!inc[i])q.push(i);int num=0;while(!q.empty()){int x=ans[++num]=q.top();q.pop();for(int i=head[x];~i;i=e[i].next){int y=e[i].t;inc[y]--;if(!inc[y])q.push(y);}}if(num<n)return 0;else return 1;}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >>T;while(T--){ct=0;cin >>n>>m;memset(head,-1,sizeof(head));memset(inc,0,sizeof(inc));for(int i=0,x,y;i<m;i++){cin >>x>>y;addedge(y,x);inc[x]++;}if(!tuopu())cout<<"Impossible!";else for(int i=n;i>0;i--)cout<<ans[i]<<' ';cout<<'\n';}return 0;}

二、洛谷1113杂物

传送门2

代码一：

#include<iostream>#include<algorithm>#include<vector>using namespace std;const int M=1e4+6;int n,len[M],vis[M],ans;vector <int> link[M];int dfs(int x){if(vis[x])return vis[x];//如果该结点被访问过,返回访问这个结点的最短时间 for(int i=0;i<link[x].size();i++)vis[x]=max(vis[x],dfs(link[x][i]));//找到所有连向这个点的边中最长的一条 vis[x]+=len[x];//加上这个结点的时间 return vis[x];}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >>n;for(int i=1,x,y;i<=n;i++){cin >>x>>len[i];while(cin>>y){if(!y)break;link[y].push_back(x);}}for(int i=1;i<=n;i++)ans=max(ans,dfs(i));cout <<ans;return 0;}

不得不说有更妙的，短小精悍，抓住了题干的输入顺序的特点Orz_Orz。这是拓扑排序吗？其实，这些代码可以认为是广义上的拓扑排序，即实现了对结点访问顺序进行排序的功能，只是实现的方式为 dfs 而已。

代码二：

#include<iostream>#include<algorithm>using namespace std;const int M=1e4+6;int n,ans[M],ma;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >>n;for(int i=1,w;i<=n;i++){cin >>i>>w;int tp=0,x;while(cin>>x&&x)tp=max(ans[x],tp);ans[i]=tp+w;ma=max(ans[i],ma);}cout<<ma;return 0;}

三、最大食物链计数【洛谷4017】

传送门3

思路：咱就是说，先把题目意思看清楚咯qwq，为啥叫最“大”食物链“计数”，可别想成是求最长食物链的长度喽。然后解释“最大食物链”是什么，首先起点一定是生产者，其次要以“不被捕食”的消费者结尾。问题就转化为了：左端点入度为0，右端点出度为0的路径数。所以我们要记录点的入度和出度，每次擦除一个(入度为0的)点时把它积累的值加入它所指向的结点里头...后面就是一顿拓扑排序的常规操作（用一个队列实现）。

#include<iostream>#include<queue>#include<vector>using namespace std;const int M=5e3+6,mod=80112002;int n,m,ind[M],oud[M],f[M],ans;vector<int> v[M];queue<int> q;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0,x,y;i<m;i++){cin>>x>>y;oud[x]++,ind[y]++;v[x].push_back(y);}for(int i=1;i<=n;i++)if(!ind[i])f[i]=1,q.push(i);while(!q.empty()){int x=q.front();q.pop();int sz=v[x].size();for(int i=0;i<sz;i++){int y=v[x][i];ind[y]--;f[y]=(f[x]+f[y])%mod;if(!ind[y])q.push(y);}}for(int i=1;i<=n;i++)if(!oud[i])ans=(ans+f[i])%mod;cout<<ans;return 0;}