题目链接：题目点这里 #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int N=100010; int p[N]; int find(int x) { if(x!=p[x]) { p[x]=find(p[x]); } return p[x]; } int n,m; int main() { cin>>n>>m; ...

给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。 现在要进行m个操作，操作共有三种： “C a b”，在点a和点b之间连一条边，a和b可能相等； “Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等； “Q2 a”，询问点a所在连通块中点的数量； 输入格式 第一行输入整数n和m。 接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。 输出格式 对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。 对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量...

题目在这里 AC代码： #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int N=100010; int d[N],p[N]; int find(int x) { if(x!=p[x]) { int t=find(p[x]); d[x]+=d[p[x]]; p[x]=t; } return p[x]; } int main() { ...

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。 注意：图中可能 存在负权回路 。 输入格式 第一行包含三个整数n，m，k。 接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 输出格式 输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。 如果不存在满足条件的路径，则输出“impossible”。 数据范围 1≤n,k≤500, 1≤m≤10000, 任意边长的绝对值不超过10000。 输入样例： 3 ...

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。 数据保证不存在负权回路。 输入格式 第一行包含整数n和m。 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 输出格式 输出一个整数，表示1号点到n号点的最短距离。 如果路径不存在，则输出”impossible”。 数据范围 1≤n,m≤105, 图中涉及边长绝对值均不超过10000。 输入样例： 3 3 1 2 5 2 3 -3 1 3 4 输出样例： 2 AC代码： #inc...

题目：给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你判断图中是否存在负权回路。 输入格式 第一行包含整数n和m。 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 输出格式 如果图中存在负权回路，则输出“Yes”，否则输出“No”。 数据范围 1≤n≤2000, 1≤m≤10000, 图中涉及边长绝对值均不超过10000。 输入样例： 3 3 1 2 -1 2 3 4 3 1 -4 输出样例： Yes #include<iostream> #include<algorithm> #inclu...

这个算法都是用在求图中任意两个点之间的距离，时间复杂度为O（n3）代码如下 #include<iostream> #include<algorithm> #include<string.h> using namespace std; int n,m,k; const int N=410; 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...

#include<iostream> #include<string.h> using namespace std; int n,m; const int N=5100; const int M=100010; int st[N],d[N]; int g[N][N]; int dijkstra() { memset(d,0x3f,sizeof(d)); d[1]=0; for(int i=1;i<=n;i++) { int t=-1; for(int j=1;j<=n;j+...

题目： 给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。 输入格式 第一行包含整数n和m。 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 输出格式 输出一个整数，表示1号点到n号点的最短距离。 如果路径不存在，则输出-1。 数据范围 1≤n,m≤105, 图中涉及边长均不小于0，且不超过10000。 输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3 时间复杂度：mlog(n); #include<iostream...

题目： 给定一个n个点m条边的有向图，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。 若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。 输入格式 第一行包含两个整数n和m 接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。 输出格式 共一行，如果存在拓扑序列，则输出拓扑序列。 否则输出-1。 数据范围 1≤n,m≤105 输入样例： 3 3 1 2 2 3 1 3 输出样例： 1 2 3 #include<iostream&g...

思路：先按照每条边的权值排序，从小到大枚举每条边，如果这条边两个顶点的祖宗节点不一样，连接上这条边并且计数器加一，最后如果计数器小于顶点个数-1的话，就说明不到n个点，就不可能，否则输出答案 代码如下： #include<iostream> using namespace std; const int N=100010; int p[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } int main() { int n;int m; while(scanf("%d&quo...

这个代码和dijkstra算法很类似。 #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int N=510; int g[N][N]; int d[N]; bool st[N]; int m,n; int prim() { memset(d,0x3f,sizeof(d)); int res=0; for(int i=0;i<n;i++) { int t=-1; ...

题目点这里 #include<iostream> #include<algorithm> #include<vector> #include<map> using namespace std; const int N=200010; int p[N]; int c[N]; int num[N]; vector<int>v[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } int main() { int n,m,k; cin&...

时间复杂度 m*n（m为边的个数，n为点的个数） #include<iostream> #include<string.h> using namespace std; const int N=510,M=100010; int e[M],ne[M],h[N],idx; bool st[N]; int match[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int n1,n2,m; bool find(int x) { for(int i=h...