Dark_Van @ 2019-02-05 15:17:18
一开始RE只有30分
后来数组开大了点,还是RE,60分,求助dalao!
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 10100;
int n,m,rud[MAX]={0};
int first[MAX];
int ans=0;
int read(){
int x=0,w=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')w=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*w;
}
struct edge{
int u,v,next;
}e[MAX];
struct node{
int u,len;
};
int cnt=0;
void insert(int u,int v){
++cnt;e[cnt].u=u;e[cnt].v=v;e[cnt].next=first[u];first[u]=cnt;
}
node makenode(int u,int len){
node qwq;
qwq.len=len;qwq.u=u;
return qwq;
}
queue<node> q;
void topo(){
for(int i=1;i<=n;i++){
if(rud[i]==0)q.push(makenode(i,1));
}
ans=1;
while(!q.empty()){
int u=q.front().u,len=q.front().len;
q.pop();
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[i].v;
rud[v]--;
if(rud[v]==0){
q.push(makenode(v,len+1));
ans=max(ans,len+1);
}
}
}
}
int con[MAX][MAX]={0};
int main(){
memset(first,-1,sizeof(first));
n=read();m=read();
int temp[MAX],stop[MAX];
for(int i=1;i<=m;i++){
memset(stop,0,sizeof(stop));
int tot=read();
for(int j=1;j<=tot;j++){
temp[j]=read();
stop[temp[j]]=1;
}
for(int j=temp[1];j<=temp[tot];j++){
if(!stop[j]){
for(int k=1;k<=tot;k++){
if(!con[j][temp[k]]){
con[j][temp[k]]=1;
insert(j,temp[k]);
rud[temp[k]]++;
}
}
}
}
}
topo();
printf("%d",ans);
return 0;
}
by 花园Serena @ 2019-02-05 16:12:04
冲您这名字就要%%%
by Dark_Van @ 2019-02-05 18:50:52
@Van♂様年华 都是同♂志
by arr2 @ 2019-02-17 08:47:10
邻接表开大 你邻接表大小就10010 我之前开到100010都re 开到1000010就好了
by 万弘 @ 2019-04-21 13:03:42
@Dark_Van 我原本也是这样,开了
before:
#define maxn 2011
#define maxm 5000011
ll n,m;
struct Edge
{
ll v,nxt;
}e[maxm];
ll cnt=0,last[maxn],ind[maxn];
void adde(ll u,ll v)
{
++ind[v];
e[++cnt].v=v;
e[cnt].nxt=last[u];last[u]=cnt;
}
after:
#define maxn 2011
#define maxm 2000011
ll n,m;
struct Edge
{
ll v,nxt;
}e[maxm];
ll cnt=0,last[maxn],ind[maxn];
bool p[maxn][maxn];
inline void adde(ll u,ll v)
{
if(p[u][v])return;
p[u][v]=1;
++ind[v];
e[++cnt].v=v;
e[cnt].nxt=last[u];last[u]=cnt;
}
PS:要稍微卡一下常,否则T一个点