CASTLE – spoj

December 21, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập thuật toán)

Code:

uses math;
const
    tfi='';//castle.inp';
    tfo='';//castle.out';
 
var
    fi,fo:text;
    n,top1,top2,top3,dem:longint;
    tg,kq1,kq2,kq11,kq22:int64;
    p,q,a,b:array[0..5001] of longint;
    st:array[0..5001] of int64;
procedure nhap;
    var i,j:longint;
    begin
        read(fi,n);
        for i:=1 to n do read(fi,a[i],b[i]);
        kq2:=high(int64);
    end;
 
procedure swap(var x,y:longint);
    var tg:longint;
    begin
        tg:=x;
        x:=y;
        y:=tg;
    end;
 
procedure sort(l,r:longint);
    var i,j,k,k1,k2:longint;
    begin
        i:=l;
        j:=r;
        k:=l+random(r-l+1);
        k1:=a[k];
        k2:=b[k];
        repeat
            while (a[i]k1) or ((a[j]=k1) and (b[j]>k2)) do dec(j);
            if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    inc(I);
                    dec(j);
                end;
        until i>j;
        if i=2 then
        begin
        tg:=int64(st[top3]-st[1])*(v-u);
        if tg=kq1 then inc(kq11);
        if tg>kq1 then
            begin
                kq1:=tg;
                kq11:=1;
            end;
        end;
        for i:=2 to top3 do
            begin
                tg:=int64(st[i]-st[i-1])*(v-u);
                if tg=kq2 then inc(kq22);
                if tga[i] then break
                    else
                        begin
                            inc(top1);
                            q[top1]:=b[j];
                        end;
                if j>n then break;
                k:=j;
                while k<=n do
                    begin
                        top2:=0;
                        for k1:=k to n+1 do
                            if a[k1]<>a[k] then break
                            else
                                begin
                                    inc(top2);
                                    p[top2]:=b[k1];
                                end;
                        lam(a[i],a[k]);
                        k:=k1;
                    end;
                i:=j;
            end;
        writeln(fo,dem);
        if dem>0 then
            begin
                writeln(fo,kq1,' ',kq11);
                writeln(fo,kq2,' ',kq22);
            end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    nhap;
    xuli;
    close(fo);
end.
Chủ đề: SPOJ, Stack Mức độ:

C11SUM – spoj

December 21, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Các bạn đọc code xem thuật toán dễ thế nào nhé 🙂

Code:

{$H+}
Uses math;
Const
	inp = '';
	out = '';
	maxn = 1000001;
	oo = 1000000007;

Var
	a,b : array [0..maxn] of int64;
	s : string;
	n,i,x : longint;
	res,hold : int64;

begin
	assign(input,inp); reset(input);
	assign(output,out); rewrite(output);
	readln(s);
	n := length(s);
	hold := 0;
	for i := 1 to n do
	  begin
	  	x := ord(s[i])-ord('0');
	  	hold := (hold*10+i*x) mod oo;
	  	res := (res +hold) mod oo;
	  end;
	writeln(res);
end.
Chủ đề: SPOJ, Toán học Mức độ:

C11BC2 – spoj

December 21, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Bài này chỉ cần LCA thôi. Dễ mà bạn tự nghĩ sẽ ra…

Code:

const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxm=trunc(1e5);
  maxp=20;
var
  link,head,ke,ts : array[-maxm..maxm] of longint;
  i,j,n,m,x,y,q,qq : longint;
  depth,cha,cau : array[1..maxn] of longint;
  p : array[1..maxn,0..maxp] of longint;
  ok : array[1..maxn,0..maxp] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v,w : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
    ts[i] := w;
  end;
procedure enter;
  var u,v ,w :longint;
  begin
    assign(input,fi);reset(input);
    readln(n,q);
    for i:=2 to n do
      begin
        read(v,w);
        add(i,i,v,w);
        add(-i,v,i,w);
      end;
  end;
procedure dfs(u : longint);
  var i,j,v : longint;
  begin
    cx[u] := false;
    i:=head[u];
    while i<>0 do
      begin
        v:=ke[i];
        if cx[v] then
        begin
          cau[v] := i;
          cha[v] := u;
          depth[v] := depth[u]+1;
          dfs(v);
        end;
        i:=link[i];
      end;
  end;
procedure init;
  var i,u : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    cha[1] := 1;
    depth[1] := 1;
    dfs(1);
    for i:=1 to n do
      begin
        p[i,0] := cha[i];
        if cau[i]<>0 then
          if ts[cau[i]]=2 then
            ok[i,0] := true;
      end;
      for i:=1 to maxp do
      for u:=1 to n do
        begin
          p[u,i] := p[p[u,i-1],i-1];
          ok[u,i] := ok[u,i] or ok[u,i-1] or ok[p[u,i-1],i-1];
        end;
  end;
function lca ( u,v : longint) : boolean;
  var res : boolean;
  begin
    res := false;
    for i:=maxp downto 0 do
      if depth[p[u,i]]>=depth[v] then
        begin
          res := res or ok[u,i];
          u := p[u,i];
        end;
    for i:=maxp downto 0 do
      if depth[p[v,i]]>=depth[u] then
        begin
          res := res or ok[v,i];
          v := p[v,i];
        end;
    if u=v then
      begin
        //writeln(u);
        exit(res);
      end;
        for i:=maxp downto 0 do
          if p[u,i]<>p[v,i] then
          begin
            res := res or ok[u,i];
            res := res or ok[v,i];
            u := p[u,i];
            v := p[v,i];
          end;
    res := res or (ok[u,0]) or (ok[v,0]);
    //writeln(cha[u]);
    exit(res);
end;
procedure process;
  var x,y : longint;
  begin
    assign(output,fo);rewrite(output);
    for qq := 1 to q do
      begin
        read(x,y);
        if lca(x,y) then writeln('YES') else writeln('NO');
      end;
    close(output);
  end;
begin
  enter;
  init;
  process;
end.
Chủ đề: LCA, SPOJ Mức độ:

Các kiểu dữ liệu trong Java

December 11, 2016 by 1 Comment

Tổng quan

Trong Java kiểu dữ liệu được chia thành hai loại:

  • Kiểu dữ liệu nguyên thủy (primitive)
    • Số nguyên (integer)
    • Số thực (float)
    • Ký tự (char)
    • Giá trị logic (boolean)
  • Kiểu dữ liệu tham chiếu (reference)
    • Mảng (array)
    • Đối tượng (object)

Kiểu dữ liệu nguyên thủy

Mọi biến đều phải khai báo một kiểu dữ liệu

  • Các kiểu dữ liệu cơ bản chứa một giá trị đơn
  • Kích thước và định dạng phải phù hợp với kiểu của nó

Java phân loại thành 4 kiểu dữ liệu nguyên thủy:

java-kieu-du-lieu-yeulaptrinh-pw

4 kiểu dữ liệu nguyên thủy trong java

Số nguyên

Số nguyên có dấu

  • Giá trị mặc định: 0
kieu-du-lieu-so-nguyen-java-yeulaptrinh-pw

Kiểu dữ liệu số nguyên (Integer)

Số thực

Số thực dấu phẩy động

  • Giá trị mặc định: 0.0
kieu-du-lieu-so-thuc-java-yeulaptrinh-pw

Kiểu dữ liệu số thực (Float)

 

 

 

Chủ đề: Java

Các kiểu dữ liệu trong C++

December 6, 2016 by Leave a Comment

Có 4 kiểu dữ liệu cơ bản trong C++ là: char, int, float, double.

kieu-du-lieu-yeulaptrinh.pw

TT Kiểu dữ liệu Kích thước              Miền giá trị
(Type) (Length) (Range)
1 unsigned char 1 byte 0 đến 255
2 char 1 byte – 128 đến 127
3 enum 2 bytes – 32,768 đến 32,767
4 unsigned int 2 bytes 0 đến 65,535
5 short int 2 bytes – 32,768 đến 32,767
6 int 2 bytes – 32,768 đến 32,767
7 unsigned long 4 bytes 0 đến 4,294,967,295
8 long 4 bytes – 2,147,483,648 đến 2,147,483,647
9 float 4 bytes 3.4 * 10–38
 đến 3.4 * 1038
10 double 8 bytes 1.7 * 10–308
 đến 1.7 * 10308
11 long double 10 bytes 3.4 * 10–4932
 đến 1.1 * 104932

Khái niệm về kiểu dữ liệu

Thông thường dữ liệu hay dùng là số và chữ. Tuy nhiên việc phân chia chỉ 2 loai dữ liệu là không đủ. Để dễ dàng hơn cho lập trình, hầu hết các NNLT đều phân chia dữ liệu thành nhiều kiểu khác nhau được gọi là các kiểu cơ bản hay chuẩn. Trên cơ sở kết hợp các kiểu dữ liệu chuẩn, NSD có thể tự đặt ra các kiểu dữ liệu mới để phục vụ cho chương trình giải quyết bài toán của mình. Có nghĩa lúc đó mỗi đối tượng được quản lý trong chương trình sẽ là một tập hợp nhiều thông tin hơn và được tạo thành từ nhiều loại (kiểu) dữ liệu khác nhau. Dưới đây chúng ta sẽ xét đến một số kiểu dữ liệu chuẩn được qui định sẵn bởi C++.

Một biến như  đã biết là một số ô nhớ liên tiếp nào đó trong bộ nhớ dùng để lưu  trữ dữ liệu (vào, ra hay kết quả trung gian) trong quá trình hoạt động của chương trình. Để quản lý chặt chẽ các biến, NSD cần khai báo cho chương trình biết trước tên biến  và kiểu của dữ liệu được chứa trong biến. Việc khai báo này sẽ làm chương trình quản lý các biến dễ dàng hơn như trong việc phân bố bộ nhớ cũng như quản lý các tính toán trên biến theo nguyên tắc: chỉ có các dữ liệu cùng kiểu với nhau mới được phép làm toán với nhau. Do đó, khi đề cập đến một kiểu chuẩn của một NNLT, thông thường chúng ta sẽ xét đến các yếu tố sau:

  • tên kiểu: là một từ dành riêng để chỉ định kiểu của dữ liệu.
  • số byte trong bộ nhớ để lưu trữ một đơn vị dữ liệu thuộc kiểu này: Thông thường số byte này phụ thuộc vào các trình biên dịch và hệ thống máy khác nhau, ở đây ta chỉ xét đến hệ thống máy PC thông dụng hiện
  • Miền giá trị của kiểu: Cho biết một đơn vị dữ liệu thuộc kiểu này sẽ có thể lấy giá trị trong miền nào, ví dụ nhỏ nhất và lớn nhất là bao nhiêu. Hiển nhiên các giá trị này phụ thuộc vào số byte mà hệ thống máy qui định cho từng kiểu. NSD cần nhớ đến miền giá trị này để khai báo kiểu cho các biến cần sử dụng một cách thích hợp.

Dưới đây là bảng tóm tắt một số kiểu chuẩn đơn giản và các thông số của nó được sử dụng trong C++.

Loại dữ liệu Tên kiểu Số ô nhớ Miền giá trị
Kí tự char 1 byte – 128 .. 127
unsigned char 1 byte 0 .. 255
Số nguyên int 2 byte – 32768 .. 32767
unsigned int 2 byte 0 .. 65535
short long 2 byte

4 byte

 – 32768 .. 32767

– 215 .. 215  – 1
Số thực float 4 byte ± 10 -37  . . ± 10 +38
double 8 byte ± 10 -307  . . ± 10 +308

Bảng 1. Các loại kiểu đơn giản

Trong chương này chúng ta chỉ xét các loại kiểu đơn giản trên đây. Các loại kiểu có cấu trúc do người dùng định nghĩa sẽ được trình bày trong các chương sau.

Kiểu ký tự

Một kí tự là một kí hiệu trong bảng mã ASCII. Như đã biết một số kí tự có mặt chữ trên bàn phím (ví dụ các chữ cái, chữ số) trong khi một số kí tự lại không (ví dụ kí tự biểu diễn việc lùi lại một ô trong văn bản, kí tự chỉ việc kết thúc một dòng hay kết thúc một văn bản). Do vậy để biểu diễn một kí tự người ta dùng chính mã ASCII của kí tự đó trong bảng mã ASCII và thường gọi là giá trị của kí tự. Ví dụ phát biểu “Cho kí  tự ‘A'” là cũng tương đương với phát biểu “Cho kí tự 65” (65 là mã ASCII của kí tự ‘A’), hoặc “Xoá kí tự xuống dòng” là cũng tương đương với phát biểu “Xoá kí tự 13” vì 13 là mã ASCII của kí tự xuống dòng.

Như vậy một biến kiểu kí tự có thể được nhận giá trị theo 2 cách tương đương – chữ hoặc giá trị số: ví dụ giả sử c là một biến kí tự thì câu lệnh gán c = ‘A’ cũng tương đương với câu lệnh gán c = 65. Tuy nhiên để sử dụng giá trị số của một kí tự c nào đó  ta phải yêu cầu đổi c sang giá trị số bằng câu lệnh int(c).

Theo bảng trên ta thấy có  2 loại kí tự là char với miền giá trị từ -128 đến   127 và unsigned char (kí tự không dấu) với miền giá trị từ 0 đến 255. Trường hợp một biến được gán giá trị vượt ra ngoài miền giá trị của kiểu thì giá trị của biến sẽ được tính theo mã bù – (256 – c). Ví dụ nếu gán cho char c giá trị 179 (vượt khỏi miền giá trị đã được qui định của char) thì giá trị thực sự được lưu trong máy sẽ là – (256 – 179) = -77.

Ví dụ 1 :

char c, d ;                                       // c, d được phép gán giá trị từ -128 đến 127

unsigned e ;                                   // e được phép gán giá trị từ 0 đến 255

c = 65 ; d = 179 ;                           // d có giá trị ngoài miền cho phép

e = 179; f = 330 ;                           // f có giá trị ngoài miền cho phép

cout << c << int(c) ;                                        // in ra chữ cái ‘A’ và giá trị số 65

cout << d << int(d) ;                                        // in ra là kí tự ‘|’ và giá trị số -77

cout << e << int(e)                                          // in ra là kí tự ‘|’ và giá trị số 179

cout << f << int(f)                          // in ra là kí tự ‘J’ và giá trị số 74

Chú ý: Qua ví dụ trên ta thấy một biến nếu được gán giá trị ngoài miền cho phép sẽ dẫn đến kết quả không theo suy nghĩ thông thường. Do vậy nên tuân thủ qui tắc chỉ gán giá trị cho biến thuộc miền giá trị mà kiểu của biến đó qui định. Ví dụ nếu muốn sử dụng biến có giá trị từ 128 .. 255 ta nên khai báo biến dưới dạng kí tự không dấu (unsigned char), còn nếu giá trị vượt quá 255 ta nên chuyển sang kiểu nguyên (int) chẳng hạn.

Kiểu số nguyên

Các số nguyên được phân chia thành 4 loại kiểu khác nhau với các miền giá trị tương ứng được cho trong bảng 1. Đó là kiểu số nguyên ngắn (short) tương đương với kiểu số nguyên (int) sử dụng 2 byte và số nguyên dài (long int) sử dụng 4 byte. Kiểu số nguyên thường được chia làm 2 loại có dấu (int) và không dấu (unsigned int hoặc có thể viết gọn hơn là unsigned). Qui tắc mã bù cũng được áp dụng nếu giá trị của biến vượt ra ngoài miền giá trị cho phép, vì vậy cần cân nhắc khi khai báo kiểu cho các  biến. Ta thường sử dụng kiểu int cho các số nguyên trong các bài toán với miền giá trị vừa phải (có giá trị tuyệt đối bé hơn 32767), chẳng hạn các biến đếm trong các vòng lặp, …

Kiểu số thực

Để sử dụng số thực ta cần khai báo kiểu float hoặc double mà miền giá trị của chúng được cho trong bảng 1. Các giá trị số kiểu double được gọi là số thực với độ chính xác gấp đôi vì với kiểu dữ liệu này máy tính có cách biểu diễn khác so với kiểu float để đảm bảo số số lẻ sau một số thực có thể tăng lên đảm bảo tính chính xác cao hơn so với số kiểu float. Tuy nhiên, trong các bài toán thông dụng thường ngày độ chính xác của số kiểu float là đủ dùng.

Như đã nhắc đến trong phần các lệnh vào/ra ở chương 1, liên quan đến việc in ấn số thực ta có một vài cách thiết đặt dạng in theo ý muốn, ví dụ độ rộng tối thiểu để in một số hay số số lẻ thập phân cần in …

Ví dụ 2 : Chương trình sau đây sẽ in diện tích và chu vi của một hình tròn có bán kính 2cm với 3 số lẻ.

#include <iostream.h>

#include <iomanip.h> void main()

{

float r = 2 ;                            // r là tên biến dùng để chứa bán kính

cout << “Diện tích = ” << setiosflags(ios::showpoint) ;

cout << setprecision(3) << r * r * 3.1416 ; getch() ;

}

 

Chủ đề: C++, Ngôn ngữ lập trình

Viết chú thích trong Java

December 3, 2016 by Leave a Comment

Viết chú thích có thể là chú thích cho dòng lệnh, chú thích cho file code…

Java hỗ trợ ba kiểu chú thích như sau:

  1. // Chú thích trên một dòng, không xuống dòng
  2. /* Chú thích một đoạn */
  3. /** Javadoc * chú thích dạng Javadoc */

note-java-yeulaptrinh.pw

Chủ đề: Java, Ngôn ngữ lập trình

PVOI14_4 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

Uses    math;
const   fi      ='';
        fo      ='';
        maxN    =5*trunc(1e4)+1;

type    arr1    =array[0..maxN] of longint;
        arr2    =array[0..maxN,1..4] of longint;

var     n       :longint;
        a       :arr1;
        T       :arr2;
        cs      :arr1;
        f       :arr2;
procedure QS(var a,cs:arr1;l,r:longint);
var     i,j,x,tg        :longint;
begin
        i:=l;j:=r;
        x:=a[l+random(r-l+1)];
        repeat
                while a[i]x do dec(j);
                if i<=j then
                begin
                        tg:=a[i];a[i]:=a[j];a[j]:=tg;
                        tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if l0 do
        begin
                Get:=Max(Get,t[x,k]);
                x:=x-x and (-x);
        end;
end;

procedure xuly;
var     i, j    :longint;
        a2 :arr1;
        dem     :longint;
        max_h   :longint;
        tmp     :longint;
        ans     :longint;
begin
        for i:=1 to n do a2[i]:=a[i];
        fillchar(t,sizeof(t),0);
        QS(a2,cs,1,n);
        dem:=1;
        a[cs[1]]:=dem;
        for i:=2 to n do
                begin
                        if a2[i]>a2[i-1] then inc(dem);
                        a[cs[i]]:=dem;
                end;
        //for i:=1 to n do write(a2[i],' ');writeln;
        max_h:=dem;
        ///// 1
        for i:=1 to n do
                begin
                        f[i,1]:=Get(a[i]-1,1)+1;
                        Update(a[i],1,f[i,1]);
                end;
        ///2
        for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],2)+1;
                        if tmp<=2 then tmp:=0;
                        begin
                                f[i,2]:=tmp;
                                Update(max_h-a[i]+1,2,max(f[i,1],f[i,2]));
                        end;
                end;
       // writeln(f[5,2]);
        ///3
         for i:=1 to n do
                begin
                        tmp:=Get(a[i]-1,3)+1;
                        if tmp<=3 then tmp:=0;

                        begin
                                f[i,3]:=tmp;
                                Update(a[i],3,max(f[i,2],f[i,3]));
                        end;
                end;
         //writeln(f[11,3]);
         //4
          for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],4)+1;
                        if tmp<=4 then tmp:=0;

                        begin
                                f[i,4]:=tmp;
                                Update(max_h-a[i]+1,4,max(f[i,3],f[i,4]));
                        end;
                end;
         // writeln(f[14,4]);
          ans:=0;
          for i:=1 to n do ans:=max(ans,f[i,4]);
          writeln(ans);
end;
procedure run;
var     i :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        cs[i]:=i;
                end;
        xuly;
        close(input);close(output);
end;

begin
        run;
end.
Chủ đề: BIT Mức độ:

PVOI14_6 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include 

using namespace std;

int factorial(int n, long long MOD) {
    int ret = 1;
    for(int i = 1; i <= n; i++) ret = ((long long)(ret) * i) % MOD;
    return ret;
}

int power(int x, int k, long long MOD) {
    if (k == 0) return 1;
    long long t = power(x, k / 2, MOD);
    t = (t * t) % MOD;
    if (k % 2 == 1) t = (t * x) % MOD;
    return t;
}

int count_in_grid(int m, int n, int s) {
    return max(0, min(max(0, s - 1), m) - max(max(0, s - n), 1) + 1);
}

int calc(int m, int n, long long MOD) {
    int x = 1;
    for(int i = 1; i < m + m; i++) {
        int j = m + m + 1 - i;
        int k = count_in_grid(m - n, m - n, j) + 2 * count_in_grid(n, m - n, j - m);
        x = ((long long)(x) * power(i, k, MOD)) % MOD;
    }
    int ret = ((long long)(factorial((long long)(m) * m - (long long)(n) * n, MOD)) * power(x, MOD - 2, MOD)) % MOD;
    return ret;
}

int main()
{
    //freopen("L.inp","r",stdin);
    //freopen("L.out","w",stdout);
	int m, n ;
	long long MOD;
    cin >> m >> n >> MOD;
    cout << calc(m, n, MOD);
}
Chủ đề: Toán học Mức độ: ,

PVOI14_3 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Ta có 1 công thức sau:

Gọi k là chi phí nhỏ nhất cần tìm.

Nếu tồn tại một chuyến đi để mất chi phí là k thì

(S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp) = k

⇔ S1 + S2 + … + Sp – k * (T1 + T2 + … + Tp) = 0

⇔ (S1 – k * T1) + (S2 – k * T2) + … + (Sp – k * Tp) = 0.

 

Giả sử tồn tại 1 chuyến đi có chi phí km < k khi đó ta có:

kmin < k = (S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp)

⇔ (S1 – kmin * T1) + (S2 – kmin * T2) + … + (Sp – kmin * Tp) > 0

 

Từ đây ta có nghĩ ra 1 thuật toán như sau.

  • Chặt nhị phân chi phí nhỏ nhất(x), với mỗi chi phí Mình tạo trọng số mỗi cho mỗi cạnh (s ,t) -> (s – x * t)
  • Nếu tồn tại 1 chu trình âm với trọng số mới -> không thể tạo ra chi phí là x.
  • Ngược lại nếu không tồn tại 1 chu trình âm nào thì kết quả cần tìm sẽ <=x
    => Chúng ta có thể sử dụng thuật toán FordBellman để tìm chu trình âm

Code:

#include 

using namespace std;

#define N 1010
#define M 10010
const double esp = 1e-5;

int n, m,  trace[N], u[M], v[M], c[M];
double d[N];

bool Ok(int x, int y) {
    while (x != 1){
        x = trace[x];
        if (x == 0) return false;
        if (x == y) return true;
    }
    return false;
}
bool FordBellman(double mid) {
    for (int i = 1; i<=n; i++) d[i] = 1e18;
    d[1] = 0;
    memset(trace, 0, sizeof trace);
    for (int i = 0; i d[x] + c[j] - mid) {
                d[y] = d[x] + c[j] - mid;
                if (Ok(x, y)) {
                    return true;
                }
                trace[y] = x;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i>u[i]>>v[i]>>c[i];
    }
    double l = 0;
    double r = 1e10;
    double cur = 0;
    while (r - l >= esp) {
        double mid = (l + r) / 2;
        if (!FordBellman(mid)) {
            cur = mid;
            l = mid;
        }else r = mid;
    }
    if (abs (cur - 1e10) <=esp) {
        cout<<"NO TOUR";
    }else
    cout<

{$MODE OBJFPC}
program SmartDogContest;
const
  InputFile  = '';
  OutputFile = '';
  maxN = 1000;
  maxM = 10000;
  maxW = 1000000000;
  maxD = (maxN + 1) * maxW;
type
  TEdge = record
    u, v, c: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[1..maxM] of TEdge;
  d: array[1..maxN + 1, 1..maxN] of Int64;
  n, m: Integer;
  BestMiu: Extended;

procedure Enter;
var
  i: Integer;
begin
  ReadLn(fi, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, c);
end;

procedure Init;
var
  i: Integer;
begin
  FillQWord(d, SizeOf(d) div 8, maxD);
  for i := 1 to n do
    d[1, i] := 0;
end;

procedure Minimize(var target: Int64; value: Int64); inline;
begin
  if target > value then target := value;
end;

procedure Optimize;
var
  k, i: Integer;
begin
  for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
    for i := 1 to m do
      with e[i] do
        Minimize(d[k, v], d[k - 1, u] + c);
end;

procedure GetBest;
var
  v, k: Integer;
  min, max, trial: Extended;
begin
  min := maxD;
  for v := 1 to n do
    if d[n + 1, v] < maxD then
      begin
        max := -maxD;
        for k := 1 to n do
          if d[k, v] < maxD then
            begin
              trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
              if max < trial then max := trial;
            end;
        if max < min then
          min := max;
      end;
  BestMiu := min;
end;

begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    Init;
    Optimize;
    GetBest;
    if BestMiu = maxD then
      Write(fo, 'NO TOUR')
    else
      Write(fo, BestMiu:0:2);
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.
Chủ đề: Đồ thị, Floyd, SPOJ Mức độ: ,

PVOI14_2 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

using namespace std;
#include
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e6;
const int INF = 1e9 + 7;
typedef pair ii;

int p[MAXN], a[1001][1001];
vector < ii > adj[MAXN];
int n, maxa;

int get(int i, int j)
{
    return (i - 1) * n + j;
}

int pa(int x)
{
    while (p[x] > 0) x = p[x];
    return x;
}

int Union(int r1, int r2)
{
    int tmp = p[r1] + p[r2];
    if (p[r1] < p[r2]){
        p[r2] = r1;
        p[r1] = tmp;
    } else{
        p[r1] = r2;
        p[r2] = tmp;
    }
    return -tmp;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
//	freopen("RSELECT.inp", "r", stdin);
  //  freopen("RSELECT.out", "w", stdout);
    cin >> n;
    FORE(i, 1, n) FORE(j, 1, n) {
        cin >> a[i][j];
        maxa = max(maxa, a[i][j]);
    }
    FORE(i, 1, n) FORE(j, 1, n){
        int u = get(i, j);
        if (i < n) adj[abs(a[i][j] - a[i + 1][j])].push_back(ii(u, get(i + 1, j)));
        if (j < n) adj[abs(a[i][j] - a[i][j + 1])].push_back(ii(u, get(i, j + 1)));
    }
    memset(p, -1, sizeof(p));
    int ans = 0;
    FORE(ll, 0, maxa){
        FOR(i, 0, adj[ll].size()) {
            p[adj[ll][i].first] = -1;
            p[adj[ll][i].second] = -1;
           // cout<
Chủ đề: Đồ thị, Kruskal Mức độ: ,