写法优美的常用函数
收录一些优美的常用函数写法。
分解质因数
有人根本不会用 do while 和 vector。
1
2
3
4
5
| vector<int> v(0);
for(int i=2;i*i<=n;i++)if(n%i==0){
v.push_back(i);
do n/=i; while(n%i==0);
}
|
SCC
缩点。
1
2
3
4
5
6
7
8
9
10
11
12
| int dfs(int u){
int low=dfn[u]=++df;st[++top]=u;
for(auto v:e[u]){
if(!dfn[v])cmin(low,dfs(v));
else if(!scc[v])cmin(low,dfn[v]);
}
if(low==dfn[u]){
++cnt;int v;
do val[cnt]+=a[v=st[top--]],scc[v]=cnt; while(v!=u);
}
return low;
}
|
最短路 Dijskstra
如果 $dis\times n\le 8\times 10^{18}$，完全可以它们压成一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| priority_queue<LL,vector<LL>,greater<LL>> q;
void dij(int s,int t){
memset(vis,0,sizeof(vis));
memset(dis,1,sizeof(dis));
while(!q.empty())q.pop();
dis[s]=0;q.push(s);
while(!q.empty()){
int u=q.top()%M;q.pop();
if(vis[u])continue;vis[u]=1;
if(vis[t])return ;
for(int i=head[u];~i;i=a[i].next){
int v=a[i].v,w=a[i].w;
if(dis[u]+w>=dis[v])continue;
dis[v]=dis[u]+w;q.push(dis[v]*M+v);
}
}
}
|