做网站工作职责,网吧网络设计方案,wordpress多媒体占用id,合肥庐江刚刚通告文章目录朴素版PrimKruskal算法染色法匈牙利算法朴素版Prim 给定一个 n 个点 m 条边的无向图#xff0c;图中可能存在重边和自环#xff0c;边权可能为负数。求最小生成树的树边权重之和#xff0c;如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G(V,E)图中可能存在重边和自环边权可能为负数。求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式
第一行包含两个整数 n 和 m。接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。输出格式
共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例
6#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510,INF 0x3f3f3f3f;int n,m;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist,0x3f,sizeof dist);int res 0;for(int i 0;i n;i){int t -1;for(int j 1;j n;j)if(!st[j] (t-1 || dist[t]dist[j]))t j;if(i dist[t] INF) return INF;if(i) res dist[t];for(int j 1;j n; j ) dist[j] min(dist[j],g[t][j]);st[t] true;}return res;
}int main()
{scanf(%d%d,n,m);memset(g,0x3f,sizeof g);while(m--){int a,b,c;scanf(%d%d%d,a,b,c);g[a][b] g[b][a] min(g[a][b],c);}int t prim();if(t INF) printf(impossible);else printf(%d\n,t);return 0;}Kruskal算法 给定一个 n 个点 m 条边的无向图图中可能存在重边和自环边权可能为负数。求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式
第一行包含两个整数 n 和 m。接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。输出格式
共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。数据范围
1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例
6#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 200010, INF 0x3f3f3f3f;int n, m;
//并查集中p
int p[N];
//不需要邻接表与图只需要一个结构体
struct Edge
{int a, b, w;//重载小于号方便排序bool operator (const Edge W)const{return w W.w;}
}edges[M];int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int kruskal()
{//排序sort(edges, edges m);for (int i 1; i n; i ) p[i] i; // 初始化并查集//res:最小生成树中所有树边的权重之和cnt当前加入了多少条边int res 0, cnt 0;//从小到大枚举所有边for (int i 0; i m; i ){int a edges[i].a, b edges[i].b, w edges[i].w;//找到集合a find(a), b find(b);//两个集合不连通if (a ! b){//合并集合p[a] b;//更新两个变量//res:最小生成树中所有树边的权重之和cnt当前加入了多少条边res w;cnt ;}}//加的边数小于n-1 说明不连通if (cnt n - 1) return INF;//输出长度之和return res;
}int main()
{scanf(%d%d, n, m);for (int i 0; i m; i ){int a, b, w;scanf(%d%d%d, a, b, w);edges[i] {a, b, w};}int t kruskal();if (t INF) puts(impossible);else printf(%d\n, t);return 0;
}染色法
染色法判断一个图是不是二分图
性质一个图是二分图当且仅当图中不含奇数环
奇数环环的边的数量是奇数
二分图把所有点分为两边使得所有边都在集合之间集合内部没有边 如果不含奇数环一定是二分图
从前向后遍历如果没有遍历过染为一种颜色将其余所有与它连通的点染为相反的颜色。
一条边的两个点一定属于不同的集合
一个连通块只要一个点确定了其余所有点的颜色都确定了
由于图中没有奇数环所以染色一定不会矛盾【反证法证明】 步骤用bfs【bfs不用手写队列代码比bfs要短】 给定一个 n 个点 m 条边的无向图图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式
第一行包含两个整数 n 和 m。接下来 m 行每行包含两个整数 u 和 v表示点 u 和点 v 之间存在一条边。输出格式
如果给定图是二分图则输出 Yes否则输出 No。数据范围
1≤n,m≤105
输入样例
4 4
1 3
1 4
2 3
2 4
输出样例
Yes#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, M 200010;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 u, int c)
{//记录当前点的颜色color[u] c;//遍历邻接点for (int i h[u]; i ! -1; i ne[i]){int j e[i];//如果没有染过颜色if (!color[j]){//染成另外一种颜色如果是1染成2如果是2染成1//如果染色失败返回falseif (!dfs(j, 3 - c)) return false;}//如果已经染过颜色判断是否矛盾即可else if (color[j] c) return false;}return true;
}int main()
{scanf(%d%d, n, m);//经常用到的邻接表存储图的方式memset(h, -1, sizeof h);while (m -- ){int a, b;scanf(%d%d, a, b);add(a, b), add(b, a);}//flag表示染的过程是否有矛盾发生bool flag true;for (int i 1; i n; i )if (!color[i]){//如果dfs返回false就定义有矛盾发生if (!dfs(i, 1)){flag false;break;}}//flag等于true过程很完美没有矛盾发生if (flag) puts(Yes);else puts(No);return 0;
}匈牙利算法
基本思路左右两边匹配成功的最大数是多少
匹配边的数量
匹配成功没有两条边共用一个点
算法思路 最坏情况下时间复杂度O(n*m)[每个男生遍历所有女生]
给定一个二分图其中左半部包含 n1 个点编号 1∼n1右半部包含 n2 个点编号 1∼n2二分图共包含 m 条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。二分图的匹配给定一个二分图 G在 G 的一个子图 M 中M 的边集 {E} 中的任意两条边都不依附于同一个顶点则称 M 是一个匹配。二分图的最大匹配所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配其边数即为最大匹配数。输入格式
第一行包含三个整数 n1、 n2 和 m。接下来 m 行每行包含两个整数 u 和 v表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。输出格式
输出一个整数表示二分图的最大匹配数。数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105
输入样例
2 2 4
1 1
1 2
2 1
2 2
输出样例
2#include cstring
#include iostream
#include algorithmusing namespace std;
//虽然是无向图只会找左边起点的边只需要存左边指向右边
const int N 510, M 100010;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]){//j为连接点的编号int j e[i];//不重复考虑if (!st[j]){//设置标志st[j] true;//如果没有匹配任何男生或者匹配的男生可以找到下家//两种情况只要有一种成功if (match[j] 0 || find(match[j])){//当前妹子匹配男生match[j] x;return true;}}}//实在不行返回falsereturn false;
}int main()
{scanf(%d%d%d, n1, n2, m);memset(h, -1, sizeof h);while (m -- ){int a, b;scanf(%d%d, a, b);add(a, b);}//res当前匹配的数量int res 0;//一次分析男生for (int i 1; i n1; i ){//将所有女生标志清空,保证只考虑一遍memset(st, false, sizeof st);//找到if (find(i)) res ;}printf(%d\n, res);return 0;
}
