Kniqht @ 2023-07-16 09:46:28
这个代码就是加入一个虚拟原点后进行topsort(减少了建图的复杂度)
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<utility>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e6+10,M=2010,inf=0x3f3f3f3f;
int n,m,a[M],s[M];
bool st[M];
int g[M][M],d[M];
void add(int a,int b,int c){
if(g[a][b]!=inf) return;
g[a][b]=c;
// e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
d[b]++;
}
int q[N];
int topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i,s[i]=1;
while(hh<=tt){
int t=q[hh++];
for(int i=1;i<=n+m;i++){
if(g[t][i]!=inf&&--d[i]==0){
q[++tt]=i;
s[i]=s[t]+g[t][i];
}
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,s[i]);
return ans;
}
signed main(){
memset(g,0x3f,sizeof(g));
scanf("%d%d",&n,&m);int t;
for(int T=1;T<=m;T++){
memset(st,0,sizeof(st));
scanf("%d",&t);
for(int i=1;i<=t;i++) scanf("%d",&a[i]),st[a[i]]=true;
for(int i=a[1];i<=a[t];i++)
if(!st[i])
add(i,T+n,1);
for(int i=1;i<=t;i++) add(T+n,a[i],0);
}
printf("%d",topsort());
return 0;
}
这个是不加虚拟原点,以前写的代码能AC(虽然感觉建图时间复杂度是有问题的)
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
int n,m;
int q[N],d[N],g[N],p[N];
bool st[N],isIn[N][N];
int topsort(){
int hh=0,tt=-1,res=0;
for(int i=1;i<=n;i++)
if(!d[i]){
q[++tt]=i;
p[i]=1;
}
while(hh<=tt){
int t=q[hh++];
for(int j=1;j<=n;j++){
if(!isIn[t][j]) continue;
if(--d[j]==0){
q[++tt]=j;
p[j]=p[t]+1;
}
}
}
for(int i=1;i<=n;i++)
res=max(res,p[i]);
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
memset(st,0,sizeof(st));
int t;
cin>>t;
for(int j=1;j<=t;j++){
cin>>g[j];
st[g[j]]=true;
}
for(int j=g[1];j<=g[t];j++)
if(!st[j])
for(int k=1;k<=t;k++)
if(!isIn[j][g[k]]){
isIn[j][g[k]]=true;
d[g[k]]++;
}
}
cout<<topsort();
return 0;
}
请问前面10pts的代码怎么改呢?