题解 P1983 【车站分级 】
引领天下
2018-08-22 19:28:41
我来这里发题解只是为了证明：某种被认为是**非正解**的算法，其实是可以AC的！
先看：https://www.luogu.org/blog/user56917/solution-p1983
其实，我并没有改动多少，只是进行了几个很常用的优化：
1. 避免重复定义变量
在原来的代码中，有一段是这样的：
```cpp
for(register int iii=1;iii<=m;iii++){
int cnt=get();
```
在这一段中，`cnt`被反复定义了$ m $次，导致了时间的浪费，因为这明明是一个可以一次解决的问题。
2. 少写头文件
你写的头文件中的函数每调用一次，编译器就载入一次，所以记住这个原则：
**$ \text{函数能手打就手打，头文件能不调用就不调用} $**
所以我省去了`iostream`头文件，没用`using namespace std;`，而是手写了`max`：`#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))`
3. 不用cin/cout
cin/cout其实很慢的，如果你被卡常了，记得换成快读/快输
经过这几个优化，就可以AC了，第8个点只用了832ms。
代码：
```cpp
#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);
}
```
恳请管理员把我这篇题解跟[这篇文章](https://www.luogu.org/blog/user56917/solution-p1983)摆在一起