Hướng dẫn giải của Tưới nước đồng cỏ


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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()

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.