P3366 【模板】最小生成树题目描述如题给出一个无向图求出最小生成树如果该图不连通则输出orz。输入格式第一行包含两个整数 N,M表示该图共有 N 个结点和 M 条无向边。接下来 M 行每行包含三个整数 Xi,Yi,Zi表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。输出格式如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz。输入输出样例输入 #1复制4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3输出 #1复制7说明/提示数据规模对于 20% 的数据N≤5M≤20。对于 40% 的数据N≤50M≤2500。对于 70% 的数据N≤500M≤104。对于 100% 的数据1≤N≤50001≤M≤2×1051≤Zi≤1041≤Xi,Yi≤N。样例解释所以最小生成树的总边权为 2237。实现代码#include iostream #include cstdio #include cstring using namespace std; const int MaxN 5000 5, MaxM 200000 5; int N, M; int U[MaxM], V[MaxM], W[MaxM]; bool used[MaxM]; int par[MaxN], Best[MaxN]; void init() { scanf(%d %d, N, M); for (int i 1; i M; i) scanf(%d %d %d, U[i], V[i], W[i]); } void init_dsu() { for (int i 1; i N; i) par[i] i; } int get_par(int x) { if (x par[x]) return x; else return par[x] get_par(par[x]); } inline bool Better(int x, int y) { if (y 0) return true; if (W[x] ! W[y]) return W[x] W[y]; return x y; } void Boruvka() { init_dsu(); int merged 0, sum 0; bool update true; while (update) { update false; memset(Best, 0, sizeof Best); for (int i 1; i M; i) { if (used[i] true) continue; int p get_par(U[i]), q get_par(V[i]); if (p q) continue; if (Better(i, Best[p]) true) Best[p] i; if (Better(i, Best[q]) true) Best[q] i; } for (int i 1; i N; i) if (Best[i] ! 0 used[Best[i]] false) { update true; merged; sum W[Best[i]]; used[Best[i]] true; par[get_par(U[Best[i]])] get_par(V[Best[i]]); } } if (merged N - 1) printf(%d\n, sum); else puts(orz); } int main() { init(); Boruvka(); return 0; }P1194 买礼物题目描述又到了一年一度的明明生日了明明想要买 B 样东西巧的是这 B 样东西价格都是 A 元。但是商店老板说最近有促销活动也就是如果你买了第 I 样东西再买第 J 样那么就可以只花 KI,J 元更巧的是KI,J 竟然等于 KJ,I。现在明明想知道他最少要花多少钱。输入格式第一行两个整数A,B。接下来 B 行每行 B 个数第 I 行第 J 个为 KI,J。我们保证 KI,JKJ,I 并且 KI,I0。特别的如果 KI,J0那么表示这两样东西之间不会导致优惠。注意 KI,J可能大于A。输出格式一个整数为最小要花的钱数。输入输出样例输入 #1复制1 1 0输出 #1复制1输入 #2复制3 3 0 2 4 2 0 2 4 2 0输出 #2复制7说明/提示样例解释 2。先买第 2 样东西花费 3 元接下来因为优惠买 1,3 样都只要 2 元共 7 元。同时满足多个“优惠”的时候聪明的明明当然不会选择用 4 元买剩下那件而选择用 2 元。数据规模对于 30% 的数据1≤B≤10。对于 100% 的数据1≤B≤500,0≤A,KI,J≤1000。2018.7.25新添数据一组实现代码#includebits/stdc.h using namespace std; struct node { int x,y,s; } d[200000]; int n,m,ans,num,f[1000],w,k,c; bool ok[1000]; bool cmp(node a,node b) { return a.sb.s; } int gf(int x) { if(f[x]x)return x; return f[x]gf(f[x]); } void work() { int x,y; for(int i1; in; i)f[i]i; for(int i1; ik-num; i) { xgf(d[i].x); ygf(d[i].y); if(x!y) { f[x]y; c; ansd[i].s; } } } int main() { cinmn; for(int i1; in; i) for(int j1; jn; j) { cinw; if(ij||w0)continue; d[k].xi; d[k].yj; d[k].sw; if(d[k].sm)num; } sort(d1,dk1,cmp); work(); if(cn-1)coutansm; else coutans(n-c)*m; return 0; }P4180 [BJWC2010] 严格次小生成树题目描述小 C 最近学了很多最小生成树的算法Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时小 P 又来泼小 C 冷水了。小 P 说让小 C 求出一个无向图的次小生成树而且这个次小生成树还得是严格次小的也就是说如果最小生成树选择的边集是 EM严格次小生成树选择的边集是 ES那么需要满足(value(e) 表示边 e 的权值) ∑e∈EMvalue(e)∑e∈ESvalue(e)。这下小 C 蒙了他找到了你希望你帮他解决这个问题。输入格式第一行包含两个整数 N 和 M表示无向图的点数与边数。接下来 M 行每行 3 个数 x,y,z 表示点 x 和点 y 之间有一条边边的权值为 z。输出格式包含一行仅一个数表示严格次小生成树的边权和。输入输出样例输入 #1复制5 6 1 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6输出 #1复制11说明/提示数据中无向图不保证无自环。对于 50% 的数据 N≤2000M≤3000。对于 80% 的数据 N≤5×104M≤105。对于 100% 的数据 N≤105M≤3×105边权 ∈[0,109]数据保证必定存在严格次小生成树。实现代码#include cstdio #include cstring #include cmath #include algorithm #include iostream #include set #include map #include queue using namespace std; typedef long long ll; const ll INF (1ll 62); #define DEBUG(x) std::cerr #x x std::endl #define int ll inline ll read() { ll f 1, x 0;char ch; do {ch getchar();if (ch -)f -1;} while (ch 9 || ch 0); do {x x * 10 ch - 0;ch getchar();} while (ch 0 ch 9); return f * x; } const int MAX_N 100000 50; const int MAX_M 300000 50; const int MAX_F 30 5; struct EDGE { int to, next, w; } edge[MAX_M 1]; int head[MAX_N], cnt; void addedge (int u, int v, int w) { edge[cnt].to v; edge[cnt].w w; edge[cnt].next head[u]; head[u] cnt; } int f[MAX_N][MAX_F], g[MAX_N][MAX_F], h[MAX_N][MAX_F], dep[MAX_N]; inline void ckmax (int x, int y) { x (x y ? x : y); } inline void dfs (int u, int fa, int w) { dep[u] dep[fa] 1; f[u][0] fa; g[u][0] w; h[u][0] -INF; for (int i 1; i 20; i ) { f[u][i] f[f[u][i - 1]][i - 1]; g[u][i] max (g[u][i - 1], g[f[u][i - 1]][i - 1]); h[u][i] max (h[u][i - 1], h[f[u][i - 1]][i - 1]); if (g[u][i - 1] g[f[u][i - 1]][i - 1]) h[u][i] max (h[u][i], g[f[u][i - 1]][i - 1]); else if (g[u][i - 1] g[f[u][i - 1]][i - 1]) h[u][i] max (h[u][i], g[u][i - 1]); } for (int i head[u]; i; i edge[i].next ) { int v edge[i].to, w edge[i].w; if (v fa) continue; dfs (v, u, w); } } inline int LCA (int x, int y) { if (dep[x] dep[y]) swap (x, y); for (int i 20; i 0; i -- ) { if (dep[f[x][i]] dep[y]) x f[x][i]; } if (x y) return x; for (int i 20; i 0; i -- ) { if (f[x][i] ! f[y][i]) { x f[x][i]; y f[y][i]; } } return f[x][0]; } int n, m, fa[MAX_N], res, sum; struct Node { int u, v, w; bool operator (const Node rhs ) const { return w rhs.w; } } a[MAX_M 1]; inline int find (int x) { return x fa[x] ? x : fa[x] find (fa[x]); } inline void merge (int x, int y) { x find (x); y find (y); if (x y) return; fa[x] y; } bool vis[MAX_M]; inline void kruskal () { n read (); m read (); for (int i 1; i m; i ) { a[i].u read (); a[i].v read (); a[i].w read (); } sort (a 1, a m 1); for (int i 1; i n; i ) fa[i] i; res 0; for (int i 1; i m; i ) { if (find (a[i].u) ! find (a[i].v)) { vis[i] 1; res ; merge (a[i].u, a[i].v); sum a[i].w; addedge (a[i].u, a[i].v, a[i].w); addedge (a[i].v, a[i].u, a[i].w); } if (res n - 1) break; } res 0; dfs (1, 0, 0); } inline int qmax (int u, int v, int maxx) { int ans -INF; for (int i 18; i 0; i -- ) { if (dep[f[u][i]] dep[v]) { if (maxx ! g[u][i]) ans max (ans, g[u][i]); else ans max (ans, h[u][i]); u f[u][i]; } } return ans; } inline void ckmin (int x, int y) { x (x y ? x : y); } inline void calc () { int ans INF; for (int i 1; i m; i ) { if (vis[i]) continue; int lca LCA (a[i].u, a[i].v); int max_u qmax (a[i].u, lca, a[i].w); int max_v qmax (a[i].v, lca, a[i].w); ckmin (ans, sum - max (max_u, max_v) a[i].w); } printf (%lld\n, ans); } signed main() { kruskal (); calc (); return 0; }P1396 营救题目背景“咚咚咚……”“查水表”原来是查水表来了现在哪里找这么热心上门的查表员啊小明感动得热泪盈眶开起了门……题目描述妈妈下班回家街坊邻居说小明被一群陌生人强行押上了警车妈妈丰富的经验告诉她小明被带到了 t 区而自己在 s 区。该市有 m 条大道连接 n 个区一条大道将两个区相连接每个大道有一个拥挤度。小明的妈妈虽然很着急但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线使得经过道路的拥挤度最大值最小。输入格式第一行有四个用空格隔开的 nmst其含义见【题目描述】。接下来 m 行每行三个整数 u,v,w表示有一条大道连接区 u 和区 v且拥挤度为 w。两个区之间可能存在多条大道。输出格式输出一行一个整数代表最大的拥挤度。输入输出样例输入 #1复制3 3 1 3 1 2 2 2 3 1 1 3 3输出 #1复制2说明/提示数据规模与约定对于 30% 的数据保证 n≤10。对于 60% 的数据保证 n≤100。对于 100% 的数据保证 1≤n≤1041≤m≤2×104w≤1041≤s,t≤n。且从 s 出发一定能到达 t 区。样例输入输出 1 解释小明的妈妈要从 1 号点去 3 号点最优路线为 1→2→3。实现代码#includebits/stdc.h using namespace std; int n,m,s,t,a[20001]; struct each { int x,y,cost; }b[20001]; bool com(each x,each y) { return x.costy.cost; } int read(){ char chgetchar(); int x0,f1; while(ch0||ch9) { if(ch-) f-1; chgetchar(); } while(ch0ch9) { xx*10ch-0; chgetchar(); } return x*f; } int find(int x){ if(a[x]0) return x; a[x]find(a[x]); return a[x]; } int main(){ nread(); mread(); sread(); tread(); for(int i1;im;i) { b[i].xread(); b[i].yread(); b[i].costread(); } sort(b1,bm1,com); for(int i1;im;i) { int Xfind(b[i].x),Yfind(b[i].y); if(X!Y) a[X]Y; if(find(s)find(t)) { coutb[i].costendl; return 0; } } return 0; }P1195 口袋的天空题目背景小杉坐在教室里透过口袋一样的窗户看口袋一样的天空。有很多云飘在那里看起来很漂亮小杉想摘下那样美的几朵云做成棉花糖。题目描述给你云朵的个数 N再给你 M 个关系表示哪些云朵可以连在一起。现在小杉要把所有云朵连成 K 个棉花糖一个棉花糖最少要用掉一朵云小杉想知道他怎么连花费的代价最小。输入格式第一行有三个数 N,M,K。接下来 M 行每行三个数 X,Y,L表示 X 云和 Y 云可以通过 L 的代价连在一起。输出格式对每组数据输出一行仅有一个整数表示最小的代价。如果怎么连都连不出 K 个棉花糖请输出No Answer。输入输出样例输入 #1复制3 1 2 1 2 1输出 #1复制1说明/提示对于 30% 的数据1≤N≤1001≤M≤103对于 100% 的数据1≤N≤1031≤M≤1041≤K≤101≤X,Y≤N0≤L104。实现代码#includebits/stdc.h using namespace std; int n,k,m; int fa[1000050]; struct node { int x; int y; int l; } a[1000005]; int cmp( const void *a , const void *b ) { struct node *c (node *)a; struct node *d (node *)b; return c-l - d-l; } int find(int x){ if(x!fa[x]) fa[x]find(fa[x]); return fa[x]; } void work(int x,int y){ xfind(x); yfind(y); if(xy) return; fa[x]y; } int main(){ cinnmk; for(int i0; im; i) { scanf(%d%d%d,a[i].x,a[i].y,a[i].l); } qsort(a,m,sizeof(a[0]),cmp); for(int i1;in;i) fa[i]i; int numn-k; int ans0; for(int i0;im;i) { if(num0) break; int aaafind(a[i].x); int wzxfind(a[i].y); if(aaa!wzx) { work(a[i].x,a[i].y); ansa[i].l; num--; } } if(num) coutNo Answerendl; else coutansendl; }
