下面的题都是
kruskal 基础题 hdu1102,hdu1233,hdu1863,hdu1875,hdu1879,hdu3371
hdu1102
#include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; /* 1102 给邻接矩阵,求最小生成树 kruskal http://www.cnblogs.com/zhourongqing/archive/2012/05/05/2484465.html 按权值排列,尽量不划圈 //或者用prim http://www.cnblogs.com/jackge/archive/2012/12/18/2823675.html */ /* 有个陷阱....想了很久的一个点,题目说a和b的范围都是1到N, 所以对点的编号不能从0开始,应该从1开始 */ const int maxn = 105; int parent[maxn]; struct node { int u, v, w; }edge[maxn*maxn];//已经有路的顶点放进集合中 bool cmp(node a, node b)//按权值的升序排 { if (a.w <= b.w) return true; return false; } /* 因为是最小生成树,所以每个分支一定要有一个根节点, 这样的话任意两个节点他们才可以根据根节点来确定是否相连 */ int find_parent(int a) //返回祖先的根节点 { if (a != parent[a]) return find_parent(parent[a]); return a; } int kruskal(int n, int cnt) { int ans = 0; sort(edge, edge + cnt, cmp); for (int i = 0; i < cnt; i++) { int x = edge[i].u; int y = edge[i].v; x = find_parent(x); y = find_parent(y); if (x != y) { ans += edge[i].w; parent[y] = x; } } return ans; } int main() { int n; while (scanf("%d", &n) != EOF)//点数 { int cnt = 0, k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &k); if (i < j) { edge[cnt].u = i; edge[cnt].v = j; edge[cnt++].w = k; } } } for (int i = 1; i <= n; i++) parent[i] = i;//点的编号只能是从1~n , 因为题目会输入边的两个端点,所以下标应该对应 int q;//已有的边 scanf("%d", &q); int a, b; for (int i = 0; i < q; i++) { scanf("%d%d", &a, &b); a = find_parent(a); b = find_parent(b); parent[b] = a; } printf("%d\n", kruskal(n, cnt)); } return 0; }
hdu1233
/* hdu 1233 最小生成树 kruskal */ #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); using namespace std; typedef long long ll; const int MAXN = 100010;//点数的最大值 const int MAXM = 20006;//边数的最大值 const int INF = 0x3f3f3f3f; const int mod = 10000007; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } const int maxn = 100 + 5; int fa[maxn]; int n; struct edges { int x, y, d; }e[maxn*(maxn-1)/2]; int cmp(edges a1, edges a2) {return a1.d < a2.d;} void init() {for (int i = 1; i <= n; i++) fa[i] = i;} int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);} void unite(int x, int y) { int tx = find(x), ty = find(y); if (tx != ty)fa[tx] = ty; } int kruskal(int num) { init(); int ans = 0; int sum = 0;//加进去的边数 for (int i = 0; i < num; i++) //num条边 { if (find(e[i].x) != find(e[i].y)) { ans += e[i].d; unite(e[i].x, e[i].y); sum++; } if (n - 1 == sum) return ans; } } int main() { //int n; 一直错这里.n只用定义一次就好...在上面定义了.如果在这里还定义会出错.. while (scanf("%d", &n) && n) { if (n == 1) { puts("0"); continue; } int bian = n*(n - 1) / 2; for (int i = 0; i < bian; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d); sort(e, e + bian, cmp); printf("%d\n", kruskal(bian)); } return 0; }
hdu1863
/* * hdu 1863 * author : mazciwong * creat on: 2016-2-4 $time$ */ #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); using namespace std; typedef long long ll; const int MAXN = 100010;//点数的最大值 const int MAXM = 20006;//边数的最大值 const int INF = 0x3f3f3f3f; const int mod = 10000007; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } const int maxn = 5500 + 5; int n, m;//这道题边用n,点用m,注意 int fa[maxn]; struct edges { int x, y, d; }e[maxn]; int cmp(edges a1, edges a2) { return a1.d < a2.d; } void init(int x) { for (int i = 1; i <= x; i++) fa[i] = i; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void unite(int x, int y) { int tx = find(x), ty = find(y); if (tx != ty)fa[tx] = ty; } int kruskal() { init(m); int ans = 0; int sum = 0;//边数 for (int i = 0; i < n; i++) { if (find(e[i].x) != find(e[i].y)) { ans += e[i].d; unite(e[i].x, e[i].y); sum++; } if (sum == m - 1) break; } if (sum != m - 1)//边数是比点少1的话,就构成最小生成树 return -1; return ans; } int main() { while (scanf("%d%d", &n, &m) != EOF&&n) { for (int i = 0; i < n; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d); sort(e, e + n, cmp); int ans = kruskal(); if (ans == -1) puts("?"); else printf("%d\n", ans); } return 0; }
hdu1875
/* * hdu 1875 * author : mazciwong * creat on: 2016-1-15 $time$ */ #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); using namespace std; typedef long long ll; const int MAXN = 100+5;//点数的最大值 const int MAXM = 10000+5;//边数的最大值 const int INF = 0x3f3f3f3f; const int mod = 10000007; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } /* http://blog.csdn.net/u013480600/article/details/38023045 两点距离 10~1000 分析:计算任意两点距离,如果合法,就添加为边,然后用kruskal解决之 */ /* 一般错误: 1.循环输入数据的时候忘记初始化 (T开大点,同组数据试多次) 2.数组开的不好 3.没用memset */ /* 找了特别久的错误!!!快一个小时 在init的初始化那里错了,别的kruskal的点是从1开始,这里是从0开始,所以初始化那里也要从0开始初始化, 一行一行调试出来的!!!! 里程: 1.发现同一段数据连续输入会出来两个结果, 2.知道是有一些变量在不同次数下会不一样, 3.开始调试,发现e[i].x和e[i].y不一样,但是第一次find也不一样,第二次find就变成一样了(具体表现在kruskal那里发现sum不会自增1,没进去那个函数) 4.这时候才发现,第二次输入这组数据直接使用了第一次的并查集,但是我每次都有init(),所以应该就是第一个数了, 5.看了一下,果然数据是从0开始的,但是init是从1~n 6.继续加油!哈哈 测试数据: 555 2 10 10 20 20 2 10 10 20 20 */ const int maxn = 100 + 5; int n, m; int fa[maxn]; struct edges { int x, y; double d; }e[MAXM]; struct point { double x, y; }p[maxn]; int cmp(edges a1, edges a2){return a1.d < a2.d;} void init(int x){for (int i = 0; i <= x; i++)fa[i] = i;} int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);} void unite(int x, int y) { int tx = find(x), ty = find(y); if (tx != ty)fa[tx] = ty; } double kruskal() { sort(e, e + m, cmp);//点边准备好 init(n); double ans = 0; int sum = 0;//边数 for (int i = 0; i < m; i++) { if (find(e[i].x) != find(e[i].y)) { ans += e[i].d; unite(e[i].x, e[i].y); sum++; } if (sum == n - 1) break; } //printf("\n%d = sum \n", sum); if (sum != n - 1)//边数是比点少1的话,就构成最小生成树 return -1.0; return ans; } double get_dist(int i, int j) //这两个点 { return sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y)); } int main() { int t; scanf("%d", &t); while(t--) { m = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); for (int i = 0; i < n; i++) //遍历所有点之间距离 { for (int j = i + 1; j < n; j++) { double len = get_dist(i, j); if (len >= 10.0&&len <= 1000.0) { e[m].x = i; e[m].y = j; e[m++].d = len; } } } // printf("\n%d= n \n", n); double ans = kruskal(); if (ans <0) puts("oh!"); else printf("%.1lf\n", ans*100); } return 0; }
hdu1879
/* * hdu 1879 * author : mazciwong * creat on: 2016-2-5 */ #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); using namespace std; typedef long long ll; const int maxn = 100+5;//点数的最大值 const int maxm = 10000+5;//边数的最大值 const int INF = 0x3f3f3f3f; const int mod = 10000007; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } /* 一般错误: 1.循环输入数据的时候忘记初始化 (T开大点,同组数据试多次) 2.数组开的不好 3.没用memset 4.kruskal中init没从0开始 */ /* 直接用Kruskal模板解决, 没有修的边,加上权值,flag变1放进去, 对于已经修建好的边,直接添加进去即可. */ int n, m; int fa[maxn]; struct edges { int x, y, d; int flag; }e[maxm]; bool cmp(edges a1, edges a2) { if (a1.flag != a2.flag) return a1.flag > a2.flag;//已经修好的边先 return a1.d < a2.d;//没边的在后面,按权值排进行kruskal } void init() { for (int i = 1; i <= n; i++) fa[i] = i; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void unite(int x, int y) { int tx = find(x), ty = find(y); if (tx != ty) fa[tx] = ty; } int kruskal() { init();//先处理点边 sort(e, e + m, cmp); int ans = 0; for (int i = 0; i < m; i++) { int tx = find(e[i].x), ty = find(e[i].y); if (tx != ty) { unite(tx, ty); if (e[i].flag == 0) ans += e[i].d; } } return ans; } int main() { while (scanf("%d", &n)!=EOF&&n) { m = n*(n - 1) / 2; for (int i = 0; i < m; i++) scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].d, &e[i].flag); printf("%d\n", kruskal()); } return 0; }
hdu3371
/* * hdu 3371 * author : mazciwong * creat on: 2016-2-5 */ #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); using namespace std; typedef long long ll; const int maxn = 500+5;//点数的最大值 const int maxm = 25000+5;//边数的最大值 const int INF = 0x3f3f3f3f; const int mod = 10000007; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } /* 一般错误: 1.循环输入数据的时候忘记初始化 (T开大点,同组数据试多次) 2.数组开的不好 3.没用memset */ //http://www.cnblogs.com/H-Vking/p/4093847.html int n, m, k;//点,可选的边,连通块个数 int fa[maxn]; struct edges { int x, y, d; }e[maxm]; bool cmp(edges a1, edges a2) { return a1.d < a2.d; } void init() { for (int i = 1; i <= n; i++) fa[i] = i; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void unite(int x, int y) { int tx = find(x), ty = find(y); if (tx != ty) fa[tx] = ty; } void kruskal() { int ans = 0; int sum = 0;//连通分块数 for (int i = 1; i <= n; i++) if (fa[i] == i) sum++; for (int i = 0; i < m; i++) { if (find(e[i].x) != find(e[i].y)) { unite(find(e[i].x), find(e[i].y)); ans += e[i].d; sum--; } if (sum == 1) //只剩下一块说明完成了 break; } if (sum > 1) puts("-1"); else printf("%d\n", ans); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i++)//未联通 scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d); init();//点边要先在这里(之前是放在kruskal函数里) sort(e, e + m, cmp);//因为下面的连通块处理那一部分就用到了fa[i]了, for (int i = 0; i < k; i++)//连通块处理,直接按照连通连线就行,放在一块,主要是处理fa[i] { int cnt; scanf("%d", &cnt); int *tmp = new int[cnt]; for (int j = 0; j < cnt; j++) { scanf("%d", &tmp[j]); if (j != 0) unite(tmp[j-1], tmp[j]); } delete[] tmp; } kruskal(); } return 0; }
