fyss006 @ 2020-03-01 10:49:27
大佬们请救救菜鸡我 思路:级别高的站点指向低级站点后topo排序 感觉复杂度没有问题
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
const int maxn=1005,maxm=1005*1005;
int head[maxn],nex[maxm],to[maxm],cnt=0;
int indegree[maxn],n,m;
bool link[maxn][maxn];
void add_edge(int u,int v){
to[++cnt]=v;
nex[cnt]=head[u];
head[u]=cnt;
indegree[v]++;
}
struct jx{
int n,t;
};
queue<jx> q;
int topo(){
int i,ans=0;
for(i=1;i<=n;i++){
if(!indegree[i]) q.push((jx){i,1});
}
while(!q.empty()){
jx y=q.front();
ans=max(ans,y.t);
//cout<<"poping"<<y.n<<" "<<y.t<<endl;
q.pop();
for(i=head[y.n];i;i=nex[i]){
int d=to[i];
indegree[d]--;
//cout<<d<<" "<<indegree[d]<<endl;
if(!indegree[d]) q.push((jx){d,y.t+1});
}
}
return ans;
}
int main(void){
int i,j,k;
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(i=1;i<=m;i++){
int t;
bool f[maxn]={false};
int fin=0,sta=0x7fffffff;
cin>>t;
for(j=1;j<=t;j++){
int v;
cin>>v;
f[v]=1;
fin=max(fin,v);
sta=min(sta,v);
}
for(j=sta;j<=fin;j++){
if(!f[j]) continue;
for(k=sta;k<=fin;k++){
if(!f[k]&&!link[j][k]) add_edge(j,k),link[j][k]=1;
}
}
}
cout<<topo();
return 0;
}
by Micro_Seven @ 2020-03-01 10:54:19
https://www.luogu.com.cn/paste/qlgb27ej
by 潜水的蒟蒻 @ 2020-03-01 11:01:56
@Micro_Seven 您都有这些了,
为什么不卡测评
by fyss006 @ 2020-03-01 11:02:27
@Micro_Seven 比赛吸不了臭氧啊233
by fyss006 @ 2020-03-01 11:03:53
求一个优化思路qwq
by Micro_Seven @ 2020-03-01 11:14:45
我是个蒟蒻,只是来凑热闹的
by _hqw_ @ 2020-03-13 19:25:02
@fyss006 考虑吸氧中毒 (逃
by djwj233 @ 2020-03-15 17:40:46
换个快读试试?