Editorial for Tưới nước đồng cỏ


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.

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='';
      oo=1000000000;
var m,n,re:longint;
    free:array[1..300] of boolean;
    d,b:array[1..300] of longint;
    a:array[1..300,1..300] of longint;

procedure rf;
var i,j:longint;
begin
      read(n);
      for i:=1 to n do read(b[i]);
      for i:=1 to n do
          for j:=1 to n do read(a[i,j]);
end;

procedure pr;
var i,j,x,mn:longint;
begin
     for i:=1 to n do
     begin
          free[i]:=true; d[i]:=b[i];
     end;
     mn:=maxlongint;
     for i:=1 to n do
         if b[i]<mn then
         begin
                mn:=b[i]; x:=i;
         end;
     free[x]:=false; re:=d[x];
     for i:=1 to n-1 do
     begin
          for j:=1 to n do
              if free[j] then
                 d[j]:=min(d[j],a[x,j]);
          mn:=oo;
          for j:=1 to n do
              if free[j] and (mn>d[j]) then
              begin
                   mn:=d[j]; x:=j;
              end;
          free[x]:=false; re:=re+d[x];
     end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 305

int c[N][N], n, d[N];
bool Free[N];

void enter() {
    scanf( "%d", &n );
    fo(i,1,n) {
        scanf ( "%d", &c[0][i] );
        c[i][0] = c[0][i];
    }
    fo(i,1,n) {
        fo(j,1,n) scanf( "%d", &c[i][j] );
        c[i][i] = INF;
    }
}

int prim() {
    fill(Free, Free+n+1, 1);
    fill(d,d+n+1,INF); d[0] = 0;
    int res = 0;
    rep(k, n+1) {
        int u, dmin = INF;
        rep(i,n+1) if( Free[i] && d[i] < dmin ) {
            dmin = d[i]; u = i;
        }
        res += d[u]; Free[u] = 0;
        rep(v,n+1) if( Free[v] && d[v] > c[u][v] ) d[v] = c[u][v];
    }
    return res;
}

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    enter();
    printf( "%d\n", prim() );
    return 0;
}

Code mẫu của ladpro98

{$MODE OBJFPC}
program fwater;
uses    math;
type    edge=record
        x,y,w:longint;
        end;
const   fi='';
        maxn=303;
        maxm=10*maxn*maxn;
var     e:array[1..maxm] of edge;
        lab:array[1..maxn] of longint;
        res,n,m:longint;

procedure input;
var     inp:text;
        i,j,c:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                readln(inp,c);
                inc(m);
                e[m].x:=n+1;
                e[m].y:=i;
                e[m].w:=c;
        end;
        for i:=1 to n do
        begin
                for j:=1 to n do
                begin
                        read(inp,c);
                        if i=j then continue;
                        inc(m);
                        e[m].x:=i;
                        e[m].y:=j;
                        e[m].w:=c;
                end;
                readln(inp);
        end;
        close(inp);
end;

procedure sort(l,r:longint);
var     i,j:longint;
        p,t:edge;
begin
        if l>=r then exit;
        i:=l;j:=r;
        p:=e[random(r-l+1)+l];
        repeat
                while e[i].w<p.w do inc(i);
                while e[j].w>p.w do dec(j);
                if i<=j then
                begin
                        if i<j then
                        begin
                                t:=e[i];
                                e[i]:=e[j];
                                e[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(p,q:longint);
begin
        if lab[p]<lab[q] then lab[q]:=p
        else
        begin
                if lab[p]=lab[q] then dec(lab[q]);
                lab[p]:=q;
        end;
end;

procedure process;
var     i,k,p,q:longint;
begin
        k:=0;
        sort(1,m);
        for i:=1 to m do
        begin
                p:=root(e[i].x);
                q:=root(e[i].y);
                if p<>q then
                begin
                        inc(k);
                        inc(res,e[i].w);
                        union(p,q);
                end;
                if k=n then exit;
        end;
end;

begin
        input;
        process;
        write(res);
end.

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=300;
var
  n:longint;
  kq:int64;
  fin,d:array[1..MAXN] of longint;
  c:array[1..MAXN,1..MAXN] of longint;
procedure inp;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do read(f,d[i]);
  for i:=1 to n do
  for j:=1 to n do
    read(f,c[i,j]);
  close(f);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure solve;
var
  i,u,v,k:longint;
begin
  kq:=0;
  for k:=1 to n do
    begin
      u:=0;
      for i:=1 to n do
        if fin[i]=0 then
          if (u=0) or (d[i]<d[u]) then u:=i;
      fin[u]:=1; kq:=kq+d[u];
      for v:=1 to n do
        if fin[v]=0 then
          d[v]:=min(d[v],c[u,v]);
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define maxn 302
#define oo 1000000000

int min(int a,int b)
{
    if(a<b)
       return a;
       else return b;
}

int main()
{
    //freopen("FWATER.in","r",stdin);
    int n;
    int a[maxn][maxn],flag[maxn],d[maxn];
    scanf("%d",&n);
    n++;a[1][1]=0;d[1]=0;flag[1]=1;
    for(int i = 2;i<=n;i++)
    {
        flag[i]=0;
        scanf("%d",&a[1][i]);
        a[i][1] = a[1][i];
        d[i] = a[1][i];
    }
    for(int i = 2;i<=n;i++)
        for(int j = 2;j<=n;j++)
            scanf("%d",&a[i][j]);
    int KQ = 0;
    while(true)
    {
               //printf("1");
        int fl = 0,minn =oo;
        for(int i=1;i<=n;i++)
        {
            if(flag[i]==0)
            {
                fl=1;
                break;
            }
        }
        if(fl==0)
           break;
        for(int i = 1;i<=n;i++)
            if(flag[i]==0 && d[i]<minn)
            {
                 fl = i;
                 minn = d[i];
            }
        KQ = KQ+d[fl];
        for(int i = 1;i<=n;i++)
            d[i] = min(d[i],a[i][fl]);
        flag[fl]=1;
    }
    printf("%d",KQ);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program FWATER;
  Const
    input  = '';
    output = '';
    maxn = 300;
    maxc = 100000000;
  Var
    a: array[0..maxn,0..maxn] of integer;
    d,trace: array[0..maxn] of integer;
    free: array[0..maxn] of boolean;
    w: array[1..maxn] of integer;
    n: integer;

Procedure init;
  Var
    f: text;
    i,j: integer;
  Begin
    Assign(f, input);
      Reset(f);

    Readln(f, n);
    For i:= 1 to n do
      Begin
        readln(f, a[0,i]);
        a[i,0]:= a[0,i];
      End;

    For i:= 1 to n do
      For j:= 1 to n do read(f, a[i,j]);

    Close(f);
  End;

Procedure Prim;
  Var
    u,v,i,k,min: integer;
  Begin
    Fillchar(free, sizeof(free), true);

    For i:= 1 to n do d[i]:= maxc;
    d[0]:= 0;

    For k:= 0 to n do
      Begin
        u:= -1;
        min:= maxc;

        For i:= 0 to n do
          if free[i] and (d[i] < min) then
            Begin
              min:= d[i];
              u:= i;
            End;

        free[u]:= false;
        For v:= 0 to n do
          if free[v] and (d[v] > a[u,v]) then
            Begin
              d[v]:= a[u,v];
              trace[v]:= u;
            End;
      End;
  End;

Procedure printresult;
  Var
    f: text;
    i,res: integer;
  Begin
    Assign(f, output);
      Rewrite(f);

      res:= 0;
      For i:= 1 to n do res:= res + a[trace[i],i];

      Writeln(f, res);
    Close(f);
  End;

Begin
  init;
  Prim;
  printresult;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX   333
using namespace std;
struct edge {
    int u,v,w;
    edge(){}
    edge(int _u,int _v,int _w) {
        u=_u;v=_v;w=_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);
    }
};
vector<edge> e;
int n;
int up[MAX];
void loadgraph(void) {
    scanf("%d",&n);
    int i,j,v;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&v);
        e.push_back(edge(0,i,v));
        e.push_back(edge(i,0,v));
    }
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1) {
            scanf("%d",&v);
            if (i!=j) e.push_back(edge(i,j,v));
        }
    for (i=0;i<=n;i=i+1) up[i]=-1;
    sort(e.begin(),e.end());
}
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 kruskal(void) {
    int i;
    int c=0;
    int s=0;
    for (i=0;i<e.size();i=i+1) {
        if (find(e[i].u)!=find(e[i].v)) {
            join(e[i].u,e[i].v);
            s=s+e[i].w;
            c=c+1;
            if (c==n) {
                printf("%d",s);
                return;
            }
        }
    }
}
int main(void) {
    //freopen("tmp.inp","r",stdin);
    loadgraph();
    kruskal();
    return 0;
}

Code mẫu của khuc_tuan

import gc  
gc.disable()  
import sys
import psyco
psyco.full() 

def main():

    n = input()
    C = [[0 for i in range(n+1)] for j in range(n+1)]

    for i in range(n):
        C[i+1][0] = C[0][i+1] = input()

    for i in range(1,n+1):
        T = [int(s) for s in raw_input().split()]
        for j in range(1,n+1):
            C[i][j] = T[j-1]

    inT = [False for i in range(n+1)]
    inT[0] = True
    nearest = [i for i in C[0]]

    total = 0

    for kk in range(n):
        min = 1000000000
        imin = -1
        for i in range(1,n+1):
            if (not inT[i]) and (nearest[i]<min):
                min = nearest[i]
                imin = i

        total += min

        assert not imin==-1

        inT[imin] = True
        for i in range(1,n+1):
            if (not inT[i]) and (C[i][imin]<nearest[i]):
                nearest[i] = C[i][imin]

    print total


main()

Comments

Please read the guidelines before commenting.


There are no comments at the moment.