书本题解爆零求调
查看原帖
书本题解爆零求调
680295
Tiger_Rory楼主2024/4/3 22:30
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std; 
bool map[1005][1005]; 
int a[1005],t[1005],into[1005],l[1005],l2[1005];              
int ans,n,m,s,o;  
void topsort() {
    int tmp,tmp2; 
    memset(l,0,sizeof(l)); tmp=0; 
    for(int i=1;i<=n;i++) if(!into[i]) {l[++tmp]=i;}
    for(ans=1;;ans++)
    {
        for(int o=1;o<=n;o++) if(into[o]>0) break; 
        if(into[o]==0)break; 
        tmp2=0; 
        for(int i=1;i<=tmp;i++) 
        for(int j=1;j<=n;j++) 
        if(map[l[i]][j]) {
            map[l[i]][j]=0; into[j]--; 
            if(!into[j]) {l2[++tmp2]=j; }
        }
        memcpy(l,l2,sizeof(l)); tmp=tmp2; 
    }
    printf("%d",ans); 
}
int main() {
    scanf("%d %d",&n,&m); int tmp=0; 
    memset(into,0,sizeof(into)); 
    memset(map,0,sizeof(map)); 
    for(int i=1;i<=m;i++) {
        scanf("%d",&s); 
        for(int j=1;j<=s;j++)
        scanf("%d",&a[j]); tmp=0; 
        for(int j=1;j<s;j++) 
            for(int k=a[j]+1;k<a[j+1];k++) {
                tmp++; 
                t[tmp]=k; 
            }
        for(int j=1;j<=s;j++) 
            for(int k=1;k<=tmp;k++) 
            if(!map[a[j]][t[k]]) {
                map[a[j]][t[k]]=1; into[t[k]]++; 
            }
    }
    topsort();                                          
    return 0; 
}

输出都是1

2024/4/3 22:30
加载中...