10.04 模板与杂记

读入优化文件版本：

 1 struct IO{
 2     char cha[1 << 26], *s;
 3     IO(){
 4         freopen("testdata.in","rb",stdin);
 5         freopen("testdata.out","w",stdout);
 6         s[fread(s=cha,1,1<<26,stdin)] = 0;
 7     }
 8     inline int read(){
 9         register num = 0;
10         while (*s < 48)
11             s++;
12         while (*s > 32)
13             num = num * 10 + *s++ - 48;
14     }
15     return num;
16 };
17 IO ip;
18 #define read ip.read

用的时候直接写a.read(),b[i].read()之类的就好。

比<queue>里面的普通队列常数小的写法（循环队列）

 1 const int maxn = (1 << 20);
 2 struct queue{
 3     int l,r,q[maxn];
 4     queue():l(1),r(0){}
 5     inline void push(int x){
 6         q[++r & (maxn-1)] = x;
 7     }
 8     inline void pop(){
 9         l++;
10     }
11     inline int front(){
12         return q[l & (maxn-1)];
13     }
14     inline bool size(){
15         retunr l <= r;
16     }
17 };

杂记方便但龟速的vector版本邻接表

突然发现vector老人家还是可以当邻接表用的。

于是心生一念随手敲一spfa板子。

1 vector <int> linker[maxn],val[maxn];
2 inline void add_edge(int from,int to,int dis){
3     linker[from].push_back(to);
4     val[from].push_back(dis);
5 }

关键代码一，建图。写法上比链表式邻接表简单许多。

 1 struct Edge{
 2     long long int from,to,dis;
 3 };
 4 Edge edge[maxn];
 5 int head[maxn];
 6 int cnt = 0;
 7 void add_edge(long long int from,long long int to,long long int dis){
 8     edge[++cnt].from = head[from];
 9     edge[cnt].to = to;
10     edge[cnt].dis = dis;
11     head[from] = cnt;
12 }

关键代码二，遍历，好像差不多。

for (int i = head[u];i!=0;i = edge[i].from){
        //邻接表，您大可为所欲为
}

for (register int i=0;i < linker[u].size();++i){
       //vector，您亦可为所欲为 
}

实际测试

邻接表十个点跑了484ms

vector不加玄学优化是1016ms

加了也有920ms，性能严重损失。

有传闻说vector在CCF的老爷机上跑得更慢，那我就更应该用链表式邻接表了。