[自用模板]持续更新！

[自用模板]持续更新！

组合数学：

求很大组合数（逆元加快速幂）

typedef long long LL;const int MOD = 1e9+7;const int MAXN = 1e6+10;LL inv[MAXN];void inverse(){ inv[1]=1; for(int i=2;i

图论：

单源最短路径spfa两种写法（dfs和bfs）

int spfa_bfs(int s){ queue q; memset(d,0x3f,sizeof(d)); d[s]=0; memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; c[s]=1; //顶点入队vis要做标记，另外要统计顶点的入队次数 int OK=1; while(!q.empty()) { int x; x=q.front(); q.pop(); vis[x]=0; //队头元素出队，并且消除标记 for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表 { int y=v[k]; if( d[x]+w[k] < d[y]) { d[y]=d[x]+w[k]; //松弛 if(!vis[y]) //顶点y不在队内 { vis[y]=1; //标记 c[y]++; //统计次数 q.push(y); //入队 if(c[y]>NN) //超过入队次数上限，说明有负环 return OK=0; } } } } return OK;}

int spfa_dfs(int u){ vis[u]=1; for(int k=f[u]; k!=0; k=e[k].next) { int v=e[k].v,w=e[k].w; if( d[u]+w < d[v] ) { d[v]=d[u]+w; if(!vis[v]) { if(spfa_dfs(v)) return 1; } else return 1; } } vis[u]=0; return 0;}

网络流

求最大流的Edmonds-Karp算法（bfs实现）const int maxn = 50 + 5;const int INF = 0x7f7f7f7f;struct Edge{ int from,to,cap,flow; Edge(int u=0,int v=0 ,int c=0,int f=0): from(u),to(v),cap(c),flow(f){}};struct EdmondsKarp{ int n,m; vector edges; vector G[maxn]; int a[maxn]; int p[maxn]; void Init(int n){ for(int i=0;i Q; Q.push(s); a[s]=INF; while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;ie.flow){ a[e.to]=min(a[x],e.cap-e.flow); p[e.to]=G[x][i]; Q.push(e.to); } } if(a[t]) break; } if(!a[t]) break; for(int u=t;u!=s;u=edges[ p[u] ].from){ edges[ p[u] ].flow+=a[t]; edges[ p[u]^1 ].flow -= a[t]; } flow += a[t]; } return flow; }};EdmondsKarp g;

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。