Editorial for Động viên đàn bò
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int N = 10100; const int M = 100010; using namespace std; int lab[N], C[N]; iii e[M]; int n, m; int root(int u) {return (lab[u] <= 0) ? u : (lab[u] = root(lab[u]));} void unite(int u, int v) {if (lab[u] > lab[v]) swap(u, v); if (lab[u] == lab[v]) lab[u]--; lab[v] = u;} int main() { ios :: sync_with_stdio(0); cin.tie(); cin >> n >> m; int u, v, L; for(int i = 1; i <= n; i++) cin >> C[i]; for(int i = 1; i <= m; i++) { cin >> u >> v >> L; e[i] = iii(C[u] + C[v] + L + L, ii(u, v)); } sort(e + 1, e + 1 + m); int cnt = 0, res = *min_element(C + 1, C + 1 + n); for(int i = 1; i <= m; i++) { u = root(e[i].Y.X); v = root(e[i].Y.Y); if (u != v) { res += e[i].X; unite(u, v); cnt++; } if (cnt == n - 1) break; } cout << res << endl; return 0; }
Code mẫu của RR
{ PROG: cheer LANG: PASCAL ID: invinci3 } const FINP=''; FOUT=''; MAXN=10011; MAXM=100011; var cost,father:array[1..MAXN] of longint; eu,ev,ec:array[1..MAXM] of longint; kq,n,m:longint; procedure inp; var f:text; i,u,v,c:longint; begin assign(f,FINP); reset(f); read(f,n,m); kq:=maxlongint; for i:=1 to n do begin read(f,cost[i]); if kq>cost[i] then kq:=cost[i]; end; for i:=1 to m do begin read(f,u,v,c); eu[i]:=u; ev[i]:=v; ec[i]:=2*c+cost[u]+cost[v]; end; close(f); end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:longint); inline; var i,j,mid:longint; begin i:=l; j:=r; mid:=ec[l+random(r-l+1)]; repeat while ec[i]<mid do inc(i); while ec[j]>mid do dec(j); if i<=j then begin swap(eu[i],eu[j]); swap(ev[i],ev[j]); swap(ec[i],ec[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure ans; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; function getRoot(u:longint):longint; begin if father[u]<0 then getRoot:=u else begin father[u]:=getRoot(father[u]); getRoot:=father[u]; end; end; procedure union(r1,r2:longint); var x:longint; begin x:=father[r1]+father[r2]; if father[r1]<father[r2] then begin father[r1]:=x; father[r2]:=r1; end else begin father[r2]:=x; father[r1]:=r2; end; end; procedure solve; var i,count,r1,r2:longint; begin for i:=1 to n do father[i]:=-1; count:=0; for i:=1 to m do begin r1:=getRoot(eu[i]); r2:=getRoot(ev[i]); if r1=r2 then continue; inc(count); inc(kq,ec[i]); if count=n-1 then break; union(r1,r2); end; end; begin inp; sort(1,m); solve; ans; end.
Code mẫu của hieult
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> //#include <conio.h> using namespace std; #define MAX(a,b) ((a>b)?a:b) #define CLEAR(A,N) (memset(A,0,(N)*sizeof(A[0]))) const int maxEdgeSize = 200005; typedef struct{ int x,y,cost; }graph; graph v[maxEdgeSize]; int ar[maxEdgeSize]; int findSet(int i){ while(ar[i]!=i) i = ar[i]; return i; } void makeUnion(int a,int p1,int b, int p2){ int x = MAX(p1,p2); ar[a] = x; ar[b] = x; ar[p1] = x; ar[p2] = x; } int adjustUsingUnionFind(int a,int b) { if(ar[a] == -1) ar[a] = a; if(ar[b] == -1) ar[b] = b; int p1 = findSet(a); int p2 = findSet(b); if(p1!=p2){ makeUnion(a,p1,b,p2); return 1; } else return 0; } bool operator < (graph a, graph b) { return a.cost < b.cost; } int main() { //freopen("QBMST.in","r",stdin); int m,n,i,minimumCost,minn = 1000000,u[20001]; scanf("%d %d",&m,&n); for(int i = 1;i<=m;i++) { scanf("%d",&u[i]); if(u[i]<minn) minn = u[i]; } // printf("1"); for(int i = 0;i<n;i++) { scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost); v[i].cost = 2*v[i].cost+u[v[i].x]+u[v[i].y]; } //printf("2"); sort(v,v+n); for(int i = 0;i<=m;i++) ar[i] = -1; minimumCost = 0; // printf("3"); for(int i = 0;i<n;i++) { if(adjustUsingUnionFind(v[i].x,v[i].y)==1) { minimumCost+= v[i].cost; //printf("%d\n",v[i].cost); } } printf("%d",minimumCost+minn); //getch(); }
Code mẫu của ll931110
program CHEER; const input = ''; output = ''; maxn = 10000; maxp = 100000; type edge = record u,v,cost: longint; end; var e: array[1..maxp] of edge; a,pr,rank: array[1..maxn] of longint; n,p: longint; res: longint; procedure init; var f: text; i: longint; begin assign(f, input); reset(f); readln(f, n, p); for i := 1 to n do read(f, a[i]); for i := 1 to p do begin read(f, e[i].u, e[i].v, e[i].cost); e[i].cost := 2 * e[i].cost + a[e[i].u] + a[e[i].v]; end; close(f); end; procedure swap(var x,y: edge); var z: edge; begin z := x; x := y; y := z; end; procedure sort(l,h: longint); var i,j: longint; t: longint; begin if l >= h then exit; i := l; j := h; t := e[random(h - l + 1) + l].cost; repeat while e[i].cost < t do inc(i); while e[j].cost > t do dec(j); if i <= j then begin if i < j then swap(e[i],e[j]); inc(i); dec(j); end; until i > j; sort(l,j); sort(i,h); end; procedure makeset(i: longint); begin pr[i] := i; rank[i] := 0; end; function root(x: longint): longint; begin if x <> pr[x] then pr[x] := root(pr[x]); root := pr[x]; end; procedure link(x,y: longint); begin if rank[x] > rank[y] then pr[y] := x else pr[x] := y; if rank[x] = rank[y] then inc(rank[y]); end; procedure union(x,y: longint); begin link(root(x),root(y)); end; procedure Kruskal; var i,cc: longint; begin cc := 0; res := 0; for i := 1 to n do if (res = 0) or (res > a[i]) then res := a[i]; for i := 1 to n do makeset(i); for i := 1 to p do begin if cc = n - 1 then break; if root(e[i].u) <> root(e[i].v) then begin res := res + e[i].cost; union(e[i].u,e[i].v); inc(cc); end; end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; sort(1,p); Kruskal; printresult; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAXV 10101 #define MAXE 200200 using namespace std; typedef long long ll; struct edge { int u,v,c; edge(){} edge(const int &_u,const int &_v,const int &_c) { u=_u;v=_v;c=_c; } bool operator < (const edge &x) const { return (c<x.c); } }; int t[MAXV]; int up[MAXV]; edge g[MAXE]; int n,m,mv; int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } int find(const int &x) { if (up[x]<0) return (x); up[x]=find(up[x]); return (up[x]); } void join(const int &a,const int &b) { int x=find(a); int y=find(b); if (x==y) return; up[y]=x; } void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); int i,u,v,c; mv=(int)1e9; for (i=1;i<=n;i=i+1) { scanf("%d",&t[i]); mv=min(mv,t[i]); } for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); scanf("%d",&c); g[i]=edge(u,v,2*c+t[u]+t[v]); } sort(&g[1],&g[m+1]); //for (i=1;i<=m;i=i+1) printf("%d %d %d\n",g[i].u,g[i].v,g[i].c); } void kruskal(void) { int i; ll res=(ll)mv; for (i=0;i<=n;i=i+1) up[i]=-1; for (i=1;i<=m;i=i+1) if (find(g[i].u)!=find(g[i].v)) { //printf("Accept %d %d %d\n",g[i].u,g[i].v,g[i].c); res+=g[i].c; join(g[i].u,g[i].v); } printf("%lld",res); } int main(void) { //freopen("tmp.txt","r",stdin); loadgraph(); kruskal(); return 0; }
Comments