Editorial for Xây dựng thành phố
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
uses math; const fi=''; var m,n,re:longint; cha,sl:array[1..1000] of longint; a,b,c:array[1..10000] of longint; procedure rf; var i:longint; begin read(n,m); for i:=1 to m do read(a[i],b[i],c[i]); end; procedure sort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=c[(i+j) shr 1]; repeat while c[i]<x do i:=i+1; while c[j]>x do j:=j-1; if i<=j then begin y:=c[i]; c[i]:=c[j]; c[j]:=y; y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; 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,x,y,dem:longint; begin sort(1,m); for i:=1 to n do begin cha[i]:=i; sl[i]:=1; end; dem:=0; i:=0; repeat i:=i+1; x:=find(a[i]); y:=find(b[i]); if x<>y then begin inc(dem); if sl[x]>sl[y] then begin cha[y]:=x; sl[x]:=sl[x]+sl[y]; end else begin cha[x]:=y; sl[y]:=sl[y]+sl[x]; end; end; until dem=n-1; writeln(c[i]); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> ii; typedef pair<int, ii> i3; #define fi first #define se second int r[1005]; i3 g[10005]; int n, m; int getRoot( int u ) { return r[u] == u ? u : r[u] = getRoot(r[u]); } int main() { scanf( "%d%d", &n, &m ); for( int i = 0; i < m; ++i ) { scanf( "%d%d%d", &g[i].se.fi, &g[i].se.se, &g[i].fi ); --g[i].se.fi; --g[i].se.se; } for( int i = 0; i < n; ++i ) r[i] = i; sort(g, g+m); int numE = 0, res; for( int i = 0; i < m && numE < n; ++i ) { int l = g[i].fi, u = g[i].se.fi, v = g[i].se.se; if (getRoot(u) != getRoot(v)) { res = l; r[r[u]] = r[v]; ++numE; } } printf( "%d\n", res ); return 0; }
Code mẫu của ladpro98
program nkcity; uses math; type e=record v,w,link:longint; end; const fi=''; maxm=23456; maxn=2345; var adj:array[1..maxm] of e; head:array[1..maxn] of longint; avail:array[1..maxn] of boolean; q:array[1..maxm] of longint; n,m,mm,maxW,res:longint; procedure input; var inp:text; i,x,y,w:longint; begin assign(inp,fi); reset(inp); readln(inp,n,mm); for i:=1 to mm do begin readln(inp,x,y,w); inc(m); adj[m].v:=y; adj[m].w:=w; adj[m].link:=head[x]; head[x]:=m; inc(m); adj[m].v:=x; adj[m].w:=w; adj[m].link:=head[y]; head[y]:=m; maxW:=max(maxW,w); end; close(inp); end; function bfs(lim:longint):boolean; var l,r,i,u:longint; begin for i:=1 to n do avail[i]:=true; l:=1;r:=1; q[1]:=1;avail[1]:=false; while l<=r do begin u:=q[l];inc(l); i:=head[u]; while i>0 do begin if (adj[i].w<=lim) and (avail[adj[i].v]) then begin inc(r); q[r]:=adj[i].v; avail[adj[i].v]:=false; end; i:=adj[i].link; end; end; for i:=1 to n do if avail[i] then exit(false); exit(true); end; procedure process; var l,r,m:longint; begin l:=1;r:=maxW; while l<=r do begin m:=(l+r) div 2; if bfs(m) then begin res:=m; r:=m-1; end else l:=m+1; end; end; begin input; process; write(res); end.
Code mẫu của RR
uses math; var res,u,v,i,n,m:longint; eu,ev,ec:array[1..10111] of longint; lab:array[1..10111] of longint; procedure swap(var a,b:longint); var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure sort(l,r:longint); 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; function getRoot(u:longint):longint; begin if lab[u]<0 then exit(u); lab[u]:=getRoot(lab[u]); exit(lab[u]); end; procedure union(r1,r2:longint); var x:longint; begin x:=lab[r1]+lab[r2]; if lab[r1]<lab[r2] then begin lab[r1]:=x; lab[r2]:=r1; end else begin lab[r2]:=x; lab[r1]:=r2; end; end; begin read(n,m); for i:=1 to m do read(eu[i],ev[i],ec[i]); sort(1,m); for i:=1 to n do lab[i]:=-1; for i:=1 to m do begin u:=getRoot(eu[i]); v:=getRoot(ev[i]); if u<>v then begin res:=max(res,ec[i]); union(u,v); end; end; writeln(res); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #define maxn 1001 #define oo 100000000 int n,m,a[maxn][maxn],d[maxn],flag[maxn],x,y,z; int min(int a,int b) { if(a<b) return a; else return b; } int main() { //freopen("NKCITY.in","r",stdin); scanf("%d %d",&n,&m); for(int i = 1;i<=n;i++) { d[i] = oo; flag[i] = 0; for(int j = 1;j<=n;j++) a[i][j] = oo; } for(int i = 1;i<=m;i++) { scanf("%d %d %d",&x,&y,&z); a[x][y] = z; a[y][x] = z; } for(int i = 1;i<=n;i++) d[i]= a[1][i]; int KQ = 0,u=1;flag[1] = 1;d[1]=0; while(true) { //printf("1"); int fl = 0, minn = oo; for(int i = 1;i<=n;i++) { if(flag[i]==0 && d[i]<minn) { fl = i; minn = d[i]; } } if(fl==0) break; else { u = fl; flag[u] = 1; if(d[fl]>KQ) KQ = d[fl]; for(int i = 1;i<=n;i++) d[i] = min(d[i],a[fl][i]); } } printf("%d",KQ); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program NKCITY; Const input = ''; output = ''; Var c: array[1..1000,1..1000] of integer; d: array[1..1000] of integer; free: array[1..1000] of boolean; n,m: integer; Procedure LoadGraph; Var f: text; i,j,u,v: integer; Begin Assign(f, input); Reset(f); Readln(f, n, m); For u:= 1 to n do For v:= 1 to n do if u = v then c[u,v]:= 0 else c[u,v]:= 1000000000; For i:= 1 to m do Begin Readln(f, u, v, c[u,v]); c[v,u]:= c[u,v]; End; Close(f); End; Procedure Prim; Var f: text; maxlen: integer; u,i,min,v,k: integer; Begin d[1]:= 0; For i:= 2 to n do d[i]:= 1000000000; maxlen:= 0; FIllchar(free, sizeof(free), true); For k:= 1 to n do Begin u:= 0; min:= 1000000000; For i:= 1 to n do if free[i] and (d[i] < min) then Begin u:= i; min:= d[i]; End; If maxlen < min then maxlen:= min; free[u]:= false; For v:= 1 to n do If free[v] and (d[v] > c[u,v]) then d[v]:= c[u,v]; End; Assign(f, output); Rewrite(f); Writeln(f, maxlen); Close(f); End; Begin LoadGraph; Prim; End.
Code mẫu của skyvn97
#include<cstdio> #include<algorithm> #define MAX 10101 using namespace std; struct edge { edge (){} int u,v,w; bool operator < (const edge &x) const { if (w<x.w) return (true); if (w>x.w) return (false); return (u+v<x.u+x.v); } }; int up[MAX]; int m,n; edge e[MAX]; void init(void) { scanf("%d",&n); scanf("%d",&m); int i; for (i=1;i<=m;i=i+1) { scanf("%d",&e[i].u); scanf("%d",&e[i].v); scanf("%d",&e[i].w); } for (i=1;i<=n;i=i+1) up[i]=-1; sort(&e[1],&e[m+1]); } 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 process(void) { int i,c; c=0; for (i=1;i<=m;i=i+1) { if (find(e[i].u)!=find(e[i].v)) { join(e[i].u,e[i].v); c=c+1; if (c==n-1) { printf("%d",e[i].w); return; } } } } int main(void) { init(); process(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <vector> using namespace std; int main() { vector<pair<int, pair<int,int> > > vec; int n, m; scanf("%d%d", &n, &m); for(int i=0;i<m ;++i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); vec.push_back( make_pair( c, make_pair( u, v))); } int f[n+1], res = 0; memset( f, -1, sizeof(int) * (n+1)); sort( vec.begin(), vec.end()); for(int i=0;i<vec.size();++i) { int u = vec[i].second.first; int v = vec[i].second.second; int c = vec[i].first; while(f[u]>=0) u = f[u]; while(f[v]>=0) v = f[v]; if(u!=v) { res = c; f[u] += f[v]; f[v] = u; } } printf("%d\n", res); return 0; }
Comments