图论之拓扑结构

有向无环图特点：（1）每个状态没有后效性

1.有向图的拓扑序列

题目链接

#include 
#include 
#include 
using namespace std;
const int N = 100010;
int e[N],ne[N],h[N],idx=0;
int q[N];
int n,m;
int d[N]={0};
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(!d[i]){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}return tt==n-1;
}int main()
{memset(h,-1,sizeof h);cin>>n>>m;int a,b;while (m -- ){cin>>a>>b;add(a,b);d[b]++;}if(!topsort())cout<<-1<<endl;else{for(int i=0;i<n;i++)cout<<q[i]<<" ";}
}

2.可达性统计

题目链接

算法：bitset+拓扑排序

#include 
#include 
#include 
#include 
using namespace std;
const int N = 30010;
int h[N],e[N],ne[N],idx=0;
int q[N];
bitset<N>f[N];
int n,m;
int d[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(d[i]==0){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);int a,b;while (m -- ){cin>>a>>b;add(a,b);d[b]++;}topsort();for(int i=n-1;i>=0;i--){int t=q[i];f[t][t]=1;for(int k=h[t];k!=-1;k=ne[k]){f[t]|=f[e[k]];}}for(int i=1;i<=n;i++)cout<<f[i].count()<<endl;
}

3.奖金

题目链接

虚拟原点建立但省略了，边的权值为正，用拓扑更简单，若为负，此题需用差分约束来写

#include 
#include 
#include 
using namespace std;
const int N = 10010,M=20010;
int h[N],e[M],ne[M],idx=0;
int q[N];
int st[N];
int d[N];
int dist[N];
int n,m;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(d[i]==0){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}return tt==n-1;
}
int main()
{memset(h,-1,sizeof h);cin>>n>>m;int a,b;while (m -- ){cin>>a>>b;add(b,a);d[a]++;}if(!topsort()){cout<<"Poor Xed"<<endl;return 0;}for(int i=1;i<=n;i++)dist[i]=100;for(int k=0;k<n;k++){int t=q[k];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];dist[j]=max(dist[j],dist[t]+1);}}int res=0;for(int i=1;i<=n;i++)res+=dist[i];cout<<res<<endl;
}

4.车站分级

题目链接

难点：建立虚拟原点否则会爆空间。

这道题很难想象用拓扑排序来做，属于一道难题

#include 
#include 
#include 
using namespace std;
const int N = 2010,M=1000010;
int n,m;
int h[N],ne[M],e[M],w[M],idx=0;
int q[N],d[N];
int dist[N];
bool st[N];void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;d[b]++;
}
bool topsort()
{int hh=0,tt=-1;for(int i=1;i<=n+m;i++){if(d[i]==0){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}
}
int main()
{memset(h,-1,sizeof h);cin>>n>>m;for(int i=1;i<=m;i++){memset(st, 0, sizeof st);int cnt,x;cin>>cnt;int start=n,end=1;while(cnt--){cin>>x;start=min(start,x);end=max(end,x);st[x]=true;}int ver=n+i;for(int j=start;j<=end;j++){if(!st[j])add(j,ver,0);else add(ver,j,1);}}topsort();for(int i=1;i<=n;i++)dist[i]=1;for(int k=0;k<n+m;k++){int t=q[k];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];dist[j]=max(dist[j],dist[t]+w[i]);}}int res=0;for(int i=1;i<=n;i++){res=max(res,dist[i]);}cout<<res<<endl;
}

5.家谱树

题目链接

#include 
#include 
#include 
using namespace std;
const int N = 110,M=N*N;
int h[N],e[M],ne[M],idx=0;
int q[N],d[N];
int n;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(d[i]==0){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}
}int main()
{cin>>n;int x;memset(h,-1,sizeof h);for(int i=1;i<=n;i++){while(cin>>x,x){add(i,x);d[x]++;}}topsort();for(int i=0;i<n;i++)cout<<q[i]<<" ";
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！