拓扑排序
只针对DAG排序
如果有环，序列长度不为(n)
时间复杂度(O(n+m))
实现：
维护每个点入度，入度为(0)的入队，每次取队首遍历出边，入度(-1)，然后继续让入度为(0)的入队，直到队空
最长路
注意(vis)过(x)才能更新(y)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
inline void Max(ll &x,ll y){if(x<y)x=y;}
int n,m,du[N];
int hd[N],to[N<<1],tot,nxt[N<<1],w[N<<1];
inline void add(int x,int y,int z) {
to[++tot]=y;w[tot]=z;nxt[tot]=hd[x];hd[x]=tot;
}
queue<int>q;
ll f[N];
bool vis[N];
int main() {
n=read();m=read();
for(int i=1;i<=m;i++) {
int u=read(),v=read(),w=read();
add(u,v,w);
du[v]++;
}
for(int i=1;i<=n;i++)
if(!du[i])
q.push(i);
f[n]=-1;vis[1]=1;
while(q.size()) {
int x=q.front();q.pop();
for(int i=hd[x];i;i=nxt[i]) {
int y=to[i];
if(vis[x]) {
Max(f[y],f[x]+w[i]);
vis[y]=1;
}
if(!--du[y]) q.push(y);
}
}
printf("%lld",f[n]);
return 0;
}
排序
很多细节
首先(n)很小，我们可以每次输入一个就拓扑一次
对于三种情况
1.如果 没有点入度为(0)，这说明有环，矛盾
如果排出序的点个数不等于已知的点，说明有环，那么显然矛盾；
2.然后除了情况1，并且入队的点(=n)，那么可以排序
3.除了上面两个就是无法排序咯——wrong 和 ok 判断如果多个点入度为0，那么我们无法确定顺序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
#define N 150
vector<int> g[N];
queue<int> q;
bool vis[N],wrong,ok;
int in[N],a[N],inc[N];
int cnt,sum;
int n,m;
char ch;
int tp(){
wrong=0;sum=0;ok=0;//ok和wrong 判断是否有多个入度为0的，无法确定顺序
for(int i=1;i<=26;i++) {
inc[i]=in[i];
if(!inc[i]&&vis[i]) {
if(!ok) ok=1;
else wrong=1;
q.push(i);
a[++sum]=i;
}
}
if(q.empty()) return 1;
while(q.size()) {
int x=q.front();q.pop();
ok=0;
for(int i=0;i<g[x].size();i++) {
int v=g[x][i];inc[v]--;
if(!inc[v]) {
q.push(v);a[++sum]=v;
if(!ok) ok=1;
else wrong=1;
}
}
}
if(cnt!=sum) return 1;
if(wrong) return 2;
return 0;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++) {
cin>>ch; x=ch-64;
if(!vis[x]){vis[x]=1;cnt++;}
cin>>ch;
cin>>ch; y=ch-64;
if(!vis[y]){vis[y]=1;cnt++;}
g[x].push_back(y);
in[y]++;
if(tp()==1) {
printf("Inconsistency found after %d relations.",i);
return 0;
}
if(sum==n&&!tp()) {
printf("Sorted sequence determined after %d relations: ",i);
for(int j=1;j<=n;j++)
printf("%c",a[j]+64);
printf(".");
return 0;
}
}
printf("Sorted sequence cannot be determined.");
return 0;
}
车站分级
解析：未停靠点向已停靠点连边，然后逐层删点删边，统计层数，最后减(1)；
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1005
using namespace std;
int in[N],n,m,s;
int tp[N][N],a[N],b[N],cnt,ans=0;
bool vis[N],is[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&s);
memset(is,0,sizeof(is));
for(int j=1;j<=s;j++)
scanf("%d",&a[j]),is[a[j]]=1;
for(int j=a[1];j<=a[s];j++)
if(!is[j])
for(int k=1;k<=s;k++)
if(!tp[j][a[k]])
tp[j][a[k]]=1,in[a[k]]++;
}
do{//cnt是点，b[cnt]是车站号
cnt=0;
for(int i=1;i<=n;i++)
if(!in[i]&&!vis[i])
vis[i]=1,b[++cnt]=i;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=n;j++)
if(tp[b[i]][j])
tp[b[i]][j]=0,in[j]--;
ans++;
}while(cnt);
printf("%d",ans-1);
return 0;
}
骑士bzoj1471
dp+拓扑
[设f[i][j]表示一个走到i，另一个走到j的方案数\
边界 f[a1][b1]=1;目标 f[a2][b2]\
然后把图拓扑排序，对于每个点，1~n暴力枚举可以到达的点，方案数累加\
注意两维都要更新
]
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 205
#define M 10005
using namespace std;
int in[N],n,m;
long long f[N][N];
int hd[M],nxt[M],to[M],tot;
inline void add(int x,int y){
to[++tot]=y;nxt[tot]=hd[x];hd[x]=tot;
}
queue<int>q;
int a1,a2,b1,b2;
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
in[y]++;
}
scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i);
f[a1][b1]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=hd[x];i;i=nxt[i]){
int y=to[i];
for(int j=1;j<=n;j++)
if(j!=y){
f[j][y]+=f[j][x];
f[y][j]+=f[x][j];
}
if(--in[y]==0) q.push(y);
}
}
printf("%lld
",f[a2][b2]);
return 0;
}
菜肴制作
建反图——最大字典序
队列代替堆
#include <queue>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2005;
const int M=10005;
inline int read() {
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void Min(int &x,int y){if(x>y)x=y;}
int n,m;
int du[N],k[N];
vector<int>G[N];
int tmp[N],st[N],tp;
#define MP make_pair
void topo() {
priority_queue< pair<int,int> >q;
memcpy(tmp,du,sizeof(tmp));
for(int i=1;i<=n;i++)
if(!tmp[i]) q.push(MP(k[i],i));
while(q.size()) {
int x=q.top().second;q.pop();
st[++tp]=x;
for(auto y:G[x])
if(!--tmp[y]) q.push(MP(k[y],y));
}
}
int work(int now) {
priority_queue< pair<int,int> >q;
int cnt=0;
memcpy(tmp,du,sizeof(tmp));
for(int i=1;i<=n;i++)
if(!tmp[i]) q.push(MP(k[i],i));
while(q.size()) {
int x=q.top().second;q.pop();
if(x==now) continue;
//先不要让他入列，直到别的都拓扑的不能再拓扑了
if(n-cnt>k[x]) return n-cnt;
cnt++;
for(auto y:G[x])
if(!--tmp[y]) q.push(MP(k[y],y));
}
return n-cnt;
}
int main() {
n=read();m=read();
for(int i=1;i<=n;i++) k[i]=read();
int x,y;
for(int i=1;i<=m;i++) {
x=read();y=read();
G[y].push_back(x);
du[x]++;
}
topo();
for(int i=n;i;i--)
printf("%d ",st[i]);
puts("");
for(int i=1;i<=n;i++)
printf("%d ",work(i));
return 0;
}
航空管制
同上
#include <queue>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2005;
const int M=10005;
inline int read() {
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void Min(int &x,int y){if(x>y)x=y;}
int n,m;
int du[N],k[N];
vector<int>G[N];
int tmp[N],st[N],tp;
#define MP make_pair
void topo() {
priority_queue< pair<int,int> >q;
memcpy(tmp,du,sizeof(tmp));
for(int i=1;i<=n;i++)
if(!tmp[i]) q.push(MP(k[i],i));
while(q.size()) {
int x=q.top().second;q.pop();
st[++tp]=x;
for(auto y:G[x])
if(!--tmp[y]) q.push(MP(k[y],y));
}
}
int work(int now) {
priority_queue< pair<int,int> >q;
int cnt=0;
memcpy(tmp,du,sizeof(tmp));
for(int i=1;i<=n;i++)
if(!tmp[i]) q.push(MP(k[i],i));
while(q.size()) {
int x=q.top().second;q.pop();
if(x==now) continue;
//先不要让他入列，直到别的都拓扑的不能再拓扑了
if(n-cnt>k[x]) return n-cnt;
cnt++;
for(auto y:G[x])
if(!--tmp[y]) q.push(MP(k[y],y));
}
return n-cnt;
}
int main() {
n=read();m=read();
for(int i=1;i<=n;i++) k[i]=read();
int x,y;
for(int i=1;i<=m;i++) {
x=read();y=read();
G[y].push_back(x);
du[x]++;
}
topo();
for(int i=n;i;i--)
printf("%d ",st[i]);
puts("");
for(int i=1;i<=n;i++)
printf("%d ",work(i));
return 0;
}