原题
1.题意分析
题意就是给你很多组数，对于每组数，有三组小数据。第一组小数据先输入一个n表示顶点数，然后再输入n-1条边表示初始边数。其它组小数据先输入一个数k，表示增加的边的数量，然后再输入k条边，表示增加的边。在输入第二组小数据时，要先把边清空，重新输入，但是边的数量不变。
2.做法
题意不难理解，说白了就是最小生成树的板子题。很明显，对于每组数，可以分为两组大数据。第一组小数据是一组大数据；第二组和第三组小数据可以分为一组大数据。对于每组大数据，求出最小生成树，再把数据清空，再求一遍。就是最终的正解了
3.关于最小生成树
板子
板子题原题
kruskal最小生成树算法的详细分析
注意输入的换行，换行卡了我10分钟
它终于来了
代码
[code]#include #include using namespace std;const int N = 1e5 + 100;int parents[N];struct edge{ int from, to, val;}edges[N];bool cmp(edge a, edge b){ if(a.val != b.val) { return a.val < b.val; }else { return a.from > b.from; } return a.to > b.to;}int cnt = 0;void add(int u, int v, int w){ cnt++; edges[cnt].from = u; edges[cnt].to = v; edges[cnt].val = w;}int Find(int n){ int last_find = n; while(true) { if(parents[n] == n || parents[n] == last_find) { return n; } last_find = n; n = parents[n]; }}int kruskal(edge* edges, int points, int bian){ int w = 0; int cur_cnt = 0; int ans = 0; sort(edges + 1, edges + bian + 1, cmp); while(cur_cnt < points-1) { w++; int node_1 = Find(edges[w].from); int node_2 = Find(edges[w].to); if(node_1 != node_2) { parents[Find(node_1)] = parents[Find(node_2)]; ans += edges[w].val; cur_cnt++; }// cout u >> v >> w; add(u, v, w); } int m; cin >> m; for(int i = 1;i > u >> v >> w; add(u, v, w); } cout |
