Editorial for Vòng đua F1
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 flashmt
const fi=''; maxn=10010; maxm=100010; var re,n,m:longint; b:array[0..maxm,0..2] of longint; cha,sl:array[1..maxn] of longint; procedure rf; var i,j:longint; begin read(n,m); for i:=1 to m do for j:=0 to 2 do read(b[i,j]); for i:=1 to n do begin cha[i]:=i; sl[i]:=1; end; end; procedure sort(l,r:longint); var i,j,x:longint; begin i:=l; j:=r; x:=b[(i+j) shr 1,2]; repeat while b[i,2]>x do i:=i+1; while b[j,2]<x do j:=j-1; if i<=j then begin b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0]; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function find(x:longint):longint; begin if cha[x]=x then find:=x else begin cha[x]:=find(cha[x]); find:=cha[x]; end; end; procedure pr; var i,j,x,y,xx,yy,dem:longint; begin sort(1,m); for i:=1 to m do begin x:=b[i,0]; y:=b[i,1]; xx:=find(x); yy:=find(y); if xx=yy then re:=re+b[i,2] else begin dem:=dem+1; if sl[xx]>=sl[yy] then begin cha[yy]:=xx; sl[xx]:=sl[xx]+sl[yy]; end else begin cha[xx]:=yy; sl[yy]:=sl[yy]+sl[xx]; end; if dem=n-1 then break; end; end; for j:=i+1 to m do re:=re+b[j,2]; writeln(re); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<algorithm> #include<functional> using namespace std; #define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 1e4 + 7; int n, m, r[N], l[N]; vector<vector<pair<int, int> > > g; bool vst[N]; void initSet(int n) { for(int i = 0; i < n; ++i) r[i] = i; } int getSet(int u) { return u == r[u] ? u : r[u] = getSet(r[u]); } void enter() { scanf("%d%d",&n,&m); g.resize(n); for(int i = 0; i < m; ++i) { int u, v, w; scanf("%d%d%d",&u,&v,&w); g[--u].push_back(make_pair(--v, w)); g[v].push_back(make_pair(u, w)); } } int dfs(const int &u, vector<pair<int, pair<int, int> > > &edge, int &sumEdge) { int res = 1; vst[u] = true; TR(g[u], it) { int v = it->first, w = it->second; if(!vst[v]) { edge.push_back(make_pair(w, make_pair(u, v))); sumEdge += w; l[v] = l[u] + 1; res += dfs(v, edge, sumEdge); } else if(l[v] < l[u] - 1) { edge.push_back(make_pair(w, make_pair(u, v))); sumEdge += w; } } return res; } void solve() { int res = 0; initSet(n); for(int u = 0; u < n; ++u) if(!vst[u]) { vector<pair<int, pair<int, int> > > edge; l[u] = 0; int n = dfs(u, edge, res), cnt = 1; sort(edge.begin(), edge.end(), greater<pair<int, pair<int, int> > >()); TR(edge, it) { int u = it->second.first, v = it->second.second, w = it->first; if(getSet(u) != getSet(v)) { res -= w; r[r[u]] = r[v]; if(++cnt == n) break; } } } printf("%d\n", res); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
{$MODE OBJFPC} program nkracing; uses math; type e=record x,y,w:longint; end; const maxn=10004; maxm=100005; fi=''; var res,n,m:longint; a:array[1..maxm] of e; lab:array[1..maxn] of longint; check:array[1..maxm] of boolean; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,n,m); for i:=1 to m do readln(inp,a[i].x,a[i].y,a[i].w); close(inp); end; procedure sort(l,r:longint); var p,i,j:longint; t:e; begin if l>=r then exit; i:=l;j:=r; p:=a[random(r-l+1)+l].w; repeat while a[i].w>p do inc(i); while a[j].w<p do dec(j); if i<=j then begin if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; function root(u:longint):longint; begin if lab[u]<=0 then exit(u); result:=root(lab[u]); lab[u]:=result; end; procedure union(u,v:longint); begin if lab[u]<lab[v] then lab[v]:=u else begin if lab[u]=lab[v] then dec(lab[v]); lab[u]:=v; end; end; procedure kruskal; var i,x,y,c:longint; begin sort(1,m); for i:=1 to m do begin x:=root(a[i].x); y:=root(a[i].y); if x<>y then begin inc(c); check[i]:=true; union(x,y); end; if c=n-1 then break; end; for i:=1 to m do if not check[i] then inc(res,a[i].w); end; begin input; kruskal; write(res); end.
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung {$R-,Q-} const FINP=''; FOUT=''; MAXN=10000; MAXM=100000; var m,n,sum,mst:longint; eu,ev,ec:array[1..MAXM] of longint; father:array[1..MAXN] of longint; procedure inp; inline; var f:text; i:longint; begin assign(f,FINP); reset(f); read(f,n,m); for i:=1 to m do read(f,eu[i],ev[i],ec[i]); sum:=0; for i:=1 to m do inc(sum,ec[i]); close(f); end; procedure ans; inline; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,sum-mst); 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[i+random(j-i+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; function getRoot(u:longint):longint; inline; 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); inline; begin if father[r1]<father[r2] then begin father[r1]:=father[r1]+father[r2]; father[r2]:=r1; end else begin father[r2]:=father[r1]+father[r2]; father[r1]:=r2; end; end; procedure solve; inline; var i,sc,u,v,r1,r2:longint; begin for i:=1 to n do father[i]:=-1; sort(1,m); sc:=0; mst:=0; for i:=1 to m do begin u:=eu[i]; v:=ev[i]; r1:=getRoot(u); r2:=getRoot(v); if r1=r2 then continue; union(r1,r2); inc(sc); inc(mst,ec[i]); if sc=n-1 then break; end; end; begin inp; 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=0,u[20001]; scanf("%d %d",&m,&n); for(int i = 0;i<n;i++) { scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost); minimumCost = minimumCost + v[i].cost; v[i].cost = -v[i].cost; } //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); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program NKRACING; const input = ''; output = ''; maxn = 10000; maxe = 1000000; var n,e: integer; u,v,cost: array[1..maxe] of integer; pr,rank: array[1..maxn] of integer; tot,tree: integer; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); readln(f, n, e); tot := 0; for i := 1 to e do begin readln(f, u[i], v[i], cost[i]); tot := tot + cost[i]; end; close(f); end; procedure sw(var x,y: integer); var z: integer; begin z := x; x := y; y := z; end; procedure swap(i,j: integer); begin sw(u[i],u[j]); sw(v[i],v[j]); sw(cost[i],cost[j]); end; procedure sort(l,h: integer); var i,j,p: integer; begin if l >= h then exit; i := l; j := h; p := cost[random(h - l + 1) + l]; repeat while cost[i] > p do inc(i); while cost[j] < p do dec(j); if i <= j then begin if i < j then swap(i,j); inc(i); dec(j); end; until i > j; sort(l,j); sort(i,h); end; function root(x: integer): integer; begin if x <> pr[x] then pr[x] := root(pr[x]); root := pr[x]; end; procedure link(x,y: integer); 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 solve; var i,nedge: integer; begin tree := 0; for i := 1 to n do begin pr[i] := i; rank[i] := 0; end; nedge := 0; for i := 1 to e do if root(u[i]) <> root(v[i]) then begin tree := tree + cost[i]; inc(nedge); link(root(u[i]),root(v[i])); end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, tot - tree); close(f); end; begin init; sort(1,e); solve; printresult; end.
Code mẫu của skyvn97
#include<cstdio> #include<algorithm> #define MAX 100100 using namespace std; 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 { if (c>x.c) return (true); if (c<x.c) return (false); return (u+v<x.u+x.v); } }; int m,n; edge lst[MAX]; int up[MAX]; int find(int x) { if (up[x]<0) return (x); up[x]=find(up[x]); return (up[x]); } void join(int a,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; for (i=1;i<=n;i=i+1) up[i]=-1; for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); scanf("%d",&c); lst[i]=edge(u,v,c); } sort(&lst[1],&lst[m+1]); } void kruskal(void) { int i; int res=0; for (i=1;i<=m;i=i+1) { if (find(lst[i].u)!=find(lst[i].v)) join(lst[i].u,lst[i].v); else res+=lst[i].c; } printf("%d",res); } int main(void) { loadgraph(); kruskal(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> using namespace std; int n, m; pair<int, pair<int,int> > a[100010]; int F[10010], result; int main() { scanf("%d%d", &n, &m); for(int i=0;i<m;++i) scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first); sort( a, a+m); memset( F, -1, sizeof(F)); for(int i=m-1;i>=0;--i) { int c = a[i].first; int u = a[i].second.first; int v = a[i].second.second; result += c; while(F[u]>=0) u = F[u]; while(F[v]>=0) v = F[v]; //cout << c << endl; if(u==v) continue; result -= c; if(F[u]>=F[v]) swap( u, v); F[u] += F[v]; F[v] = u; } cout << result << endl; //system("pause"); return 0; }
Comments