Editorial for Yugi-Oh
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
#include<iostream> #include<algorithm> #include<cstring> #define fr(a,b,c) for(a=b;a<=c;a++) using namespace std; int n,k,sm,re,d[222],a[222][222]; void dfs(int x,int val) { int i; d[x]=1; fr(i,1,n) if (!d[i] && a[x][i]<val) dfs(i,val); } int main() { int i,j; cin >> n >> k; fr(i,1,n) fr(j,1,n) cin >> a[i][j]; int l=0,r=32767; while (l<=r) { int m=(l+r)/2; memset(d,0,sizeof(d)); sm=0; fr(i,1,n) if (!d[i]) dfs(i,m),sm++; if (sm>=k) { re=m; l=m+1; } else r=m-1; } cout << re << endl; return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> const int N = 222; using namespace std; int a[N][N]; int n, k; struct disjoint_set { int lab[N]; disjoint_set() {for(int i = 1; i <= n; i++) lab[i] = 0;} int root(int u) {return lab[u] <= 0 ? u : (lab[u] = root(lab[u]));} void join(int u, int v) {if (lab[u] > lab[v]) swap(u, v); if (lab[u] == lab[v]) lab[u]--; lab[v] = u;} }; int cnt(int lim) { disjoint_set dsu; int cc = n; for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if (a[i][j] < lim) { int x = dsu.root(i), y = dsu.root(j); if (x != y) { dsu.join(x, y); cc--; } } return cc; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; int l = 0, r = 1 << 16, m, res = 0; while (l <= r) { m = l + r >> 1; if (cnt(m) >= k) { res = m; l = m + 1; } else r = m - 1; } cout << res; return 0; }
Code mẫu của RR
{$R+,Q+} PROGRAM YUGI; CONST FINP=''; FOUT=''; maxn=200; maxm=20000; oo=1000000; VAR c:array[1..maxn,1..maxn] of longint; hu,hv:array[1..maxm] of longint; eu,ev,father:array[1..maxn] of longint; n,k,hsize:longint; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure downHeap(i:longint); var j:longint; begin j:=i shl 1; while j<=hsize do begin if (j<hsize) and (c[hu[j+1],hv[j+1]]<c[hu[j],hv[j]]) then inc(j); if (c[hu[j],hv[j]]<c[hu[i],hv[i]]) then begin swap(hu[j],hu[i]); swap(hv[j],hv[i]); end; i:=j; j:=i shl 1; end; end; procedure upHeap(i:longint); var j:longint; begin j:=i shr 1; while (j>=1) and (c[hu[j],hv[j]]>c[hu[i],hv[i]]) do begin swap(hu[i],hu[j]); swap(hv[i],hv[j]); i:=j; j:=i shr 1; end; end; procedure push(u,v:longint); begin inc(hsize); hu[hsize]:=u; hv[hsize]:=v; upHeap(hsize); end; procedure pop(var u,v:longint); begin u:=hu[1]; v:=hv[1]; swap(hu[hsize],hu[1]); swap(hv[hsize],hv[1]); dec(hsize); downHeap(1); end; procedure readInput; var f:text; i,j:longint; begin assign(f,FINP); reset(f); readln(f,n,k); for i:=1 to n do for j:=1 to n do begin read(f,c[i,j]); if i<j then push(i,j); end; close(f); end; function getRoot(u:longint):longint; begin while father[u]>0 do u:=father[u]; getRoot:=u; end; procedure union(r1,r2:longint); var x:longint; begin x:=father[r1]+father[r2]; if father[r1]<father[r2] then begin father[r2]:=r1; father[r1]:=x; end else begin father[r1]:=r2; father[r2]:=x; end; end; procedure Kruskal; var i,r1,r2,u,v,count:longint; begin for i:=1 to n do father[i]:=-1; count:=0; while hsize>0 do begin pop(u,v); r1:=getRoot(u); r2:=getRoot(v); if r1<>r2 then begin inc(count); eu[count]:=u; ev[count]:=v; if count=n-1 then exit; union(r1,r2); end; end; end; function min(a,b:longint):longint; begin if a<b then min:=a else min:=b; end; procedure writeOutput; var ans,i:longint; f:text; begin assign(f,FOUT); rewrite(f); ans:=oo; for i:=n-1 downto n-k+1 do ans:=min(ans,c[eu[i],ev[i]]); writeln(f,ans); close(f); end; BEGIN readInput; Kruskal; writeOutput; END.
Code mẫu của ll931110
#include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; int a[202][202]; bool chs[202]; int n,k; bool ok(int x) { memset(chs,false,sizeof(chs)); int gr = 0; for (int i = 1; i <= n; i++) if (!chs[i]) { gr++; if (gr == k) return true; chs[i] = true; queue<int> q; q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 1; v <= n; v++) if (!chs[v] && a[u][v] < x) { chs[v] = true; q.push(v); }; }; }; return false; }; int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); int inf = 0; int sup = 32767; int ret = 0; while (inf <= sup) { int med = (inf + sup) / 2; if (ok(med)) { ret = med; inf = med + 1; } else sup = med - 1; }; printf("%d\n", ret); };
Comments