题解 P1983 【车站分级】

发表于 更新于 阅读次数： Waline：
P1983 【车站分级】题解。

我来这里发题解只是为了证明：某种被认为是非正解的算法，其实是可以AC的！

先看：https://www.luogu.org/blog/user56917/solution-p1983

其实，我并没有改动多少，只是进行了几个很常用的优化：

  1. 避免重复定义变量

在原来的代码中，有一段是这样的：

1
2
for(register int iii=1;iii<=m;iii++){
      int cnt=get();

在这一段中，cnt被反复定义了$ m $次，导致了时间的浪费，因为这明明是一个可以一次解决的问题。

  1. 少写头文件

你写的头文件中的函数每调用一次，编译器就载入一次，所以记住这个原则：

$ \text{函数能手打就手打，头文件能不调用就不调用} $

所以我省去了iostream头文件，没用using namespace std;，而是手写了max：#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))

  1. 不用cin/cout

cin/cout其实很慢的，如果你被卡常了，记得换成快读/快输

经过这几个优化，就可以AC了，第8个点只用了832ms。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y))))) //手写max
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//快读/快输
int que[100000000],dis[2011],v[1011][1011],ints[10000],qian[1011][1011],n,m,ans,cnt;//变量尽量一次定义
unsigned char bv[2011],G[1011][1011],st[2011];
inline void add(int s,int t,int l){
    G[s][t]=1;
    v[s][t]=max(v[s][t],l);
}
int main(){
    read(n),read(m);
    for(register int iii=1;iii<=m;iii++){
        read(cnt);
        memset(bv,0,sizeof(bv));
        for(register int i=1;i<=cnt;i++)read(ints[i]),bv[ints[i]]=1;
        for(register int i=1;i<=cnt;i++)
        for(register int j=ints[1];j<=ints[cnt];j++)if(!bv[j])add(j,ints[i],1);
    }//register定义变量很快的
    memset(bv,0,sizeof(bv));
    for(register int i=1;i<=n+1;i++)dis[i]=-1234567890;
    register int head=0,tail=1;que[0]=n+1;
    dis[n+1]=0;
    for(register int i=1;i<=n;i++)add(n+1,i,1);
    for(register int i=1;i<=n+1;i++)
    for(register int j=1;j<=n+1;j++)
    if(i!=j&&G[i][j])qian[i][0]++,qian[i][qian[i][0]]=j;
    do{
        int me=que[head];head++;bv[me]=0;
        for(register int j=1;j<=qian[me][0];j++){
            int i=qian[me][j];
            if(dis[me]+v[me][i]>dis[i]){
                dis[i]=dis[me]+v[me][i];
                if(!bv[i])bv[i]=1,que[tail++]=i;
            }
        }
    }while(head<tail);
    for(register int i=1;i<=n;i++)st[dis[i]]=1;
    for(register int i=1;i<=1000;i++)ans+=st[i];
    write(ans);
    return(0);
}

原解法：这篇文章摆在一起