AcWing 867. 分解质因数 #include <bits/stdc++.h> using namespace std; int n; void divided(int x){ for(int i=2;i<=x/i;i++) { if(x%i==0) { //指数 int s=0; while(x%i==0) { x...

AcWing 866. 试除法判定质数 #include <bits/stdc++.h> using namespace std; int n; bool prime(int x){ if(x<2) return false; for(int i=2;i<=x/i;i++){ if(x%i==0) return false; } return true; } int main(){ cin>>n; while(n--){ int x; scanf(&quot...

AcWing 861. 二分图的最大匹配 #include <bits/stdc++.h> using namespace std; const int N=510,M=2e5+10; int n1,n2,m; int h[N],e[M],ne[M],idx; int match[N]; bool st[N]; void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool find(int x){ for(int i=h[x];i!=-1;i=ne[i]){ ...

AcWing 860. 染色法判定二分图 #include <bits/stdc++.h> using namespace std; const int N=1e5+10,M=2e5+10; int n,m; int h[N],e[M],ne[M],idx; int color[N]; void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool dfs(int a,int b){ color[a]=b; for(int i=h[a];i!=-1;i=ne[i]){ ...

AcWing 859. Kruskal算法求最小生成树 #include <bits/stdc++.h> using namespace std; const int N=2e5+10; int n,m; int p[N]; struct Node{ int a,b,w; bool operator< (const Node &W)const{ return w<W.w; } }nodes[N]; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); retur...

AcWing 858. Prim算法求最小生成树 //y总做法 #include <bits/stdc++.h> using namespace std; const int N = 510,INF=0x3f3f3f3f; int n, m; int g[N][N]; bool st[N]; int dist[N]; int prim() { memset(dist, 0x3f, sizeof dist); int res = 0; dist[n]=0; for (int i = 0; i < n; i++) { int ...

AcWing 854. Floyd求最短路 #include <bits/stdc++.h> using namespace std; const int N=210,INF=1e9; int n,m,Q; int d[N][N]; void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int m...

AcWing 852. spfa判断负环 #include <bits/stdc++.h> using namespace std; const int N=1e6+10; typedef pair<int,int> PII; int n,m; int h[N],e[N],ne[N],w[N],idx; int dist[N],cnt[N]; bool st[N]; void add(int a,int b,int c){ e[idx]=b; ne[idx]=h[a]; w[idx]=c; h[a]=idx++; } bool sp...

AcWing 853. 有边数限制的最短路 #include <bits/stdc++.h> using namespace std; const int N=5e2+10,M=1e4+10; int dist[N],backup[N]; int n,m,k; struct Node{ int a,b,w; }nodes[M]; int bellman_ford(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<k;i++){ memcpy(backup,...

AcWing打卡记录(持续更新中) 题号 打卡随笔 89 AcWing 89. a^b 90 AcWing 90. 64位整数乘法 91 AcWing 91. 最短Hamilton路径 143 AcWing 143. 最大异或对 154 AcWing 154. 滑动窗口 240 AcWing 240. 食物链 785 AcWin...

AcWing 850. Dijkstra求最短路 II #include <bits/stdc++.h> using namespace std; const int N=1e6+10; typedef pair<int,int> PII; int n,m; int h[N],e[N],ne[N],w[N],idx; int dist[N]; bool st[N]; void add(int a,int b,int c){ e[idx]=b; ne[idx]=h[a]; w[idx]=c; h[a]=idx++; } int dij...

AcWing 849. Dijkstra求最短路 I #include <bits/stdc++.h> using namespace std; const int N=5e2+10; int n,m; int g[N][N]; int dist[N]; bool st[N]; int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=1;i<n;i++){ //全局最小值点 int t=-1; for(int j=1;j...

AcWing 844. 走迷宫 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=1e2+10; int n,m; int g[N][N]; int d[N][N]; PII q[N*N]; // PII Prev[N][N]; int bfs(){ int hh=0,tt=0; q[0]={0,0}; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; memset(d,-1,sizeo...

AcWing 848. 有向图的拓扑序列 #include <bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m; int h[N],e[N],ne[N],idx; // d是入度 int q[N],d[N]; void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool topsort(){ int hh=0,tt=-1; for(int i=1;i<=n;i++){ ...