UPGRANET – spoj

August 12, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Ta thấy thông lượng truyền tin từ u đến v là giá trị lớn nhất của cạnh nhỏ nhất trên mọi con đường từ u đến v.
Vì vậy, ban đầu, ta sẽ xây dựng cây khung lớn nhất(tương tự như cây khung nhỏ nhất nhưng sort ngược lại).

Gọi dis(u,v) là cạnh có trọng số nhỏ nhất khi đi từ u đến v trên cây vừa tạo. Ta chọn nút 1 làm gốc, duyệt dfs để lưu trữ cạnh nhỏ nhất và các nút cha của u khi đi từ 1 đến u (đều dùng RMQ). Với mỗi 1 cạnh không nằm trong cây khung, ta tìm nút cha chung gần nhất(gọi là p), kết quả cộng thêm một lượng bằng hiệu của min(dis(u, p), dis(v, p)) và rọng số cạnh đang xét.

Code:

#include 
#define maxn 1000005
#define maxm 10000005
#define maxc 1000000007
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair
#define fort(i, a, b) for(int i = (a); i <= (b); i++)
#define ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Task "UPGRANET"
#define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define stop1 {cout << "-1\n"; return;}
#define stop2 {cout << "0\n"; return;}
#define stop3 {cout << "yes\n"; exit(0);}
#define skip1 {cout << "Yes\n"; continue;}
#define skip2 {cout << "No\n"; continue;}
#define ll long long

using namespace std;

ll n, m, root[maxn], h[maxn], res;
pii  par[maxn][20];
bool dd[maxn];
vector > ke[maxn];
struct canh
{
    ll u, v, w;
}ed[maxn];

void setup()
{
    cin >> n >> m;
    fort(i, 1, m)
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
}

bool cmp(canh p, canh q)
{
    return p.w > q.w;
}

ll getroot(ll u)
{
    if(root[u] == 0) return u;
    return root[u] = getroot(root[u]);
}

void make_tree()
{
    sort(ed+1, ed+m+1, cmp);
    fort(i, 1, m)
    {
        ll p = getroot(ed[i].u);
        ll q = getroot(ed[i].v);
        if(p == q) continue;
        root[p] = q;
        dd[i] = 1;
        ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
        ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
    }
}

void dfs(ll u, ll tr)
{
    fort(i, 0, int(ke[u].size()) - 1)
    {
        ll v = ke[u][i].F;
        if(v == tr) continue;
        h[v] = h[u] + 1;
        par[v][0] = mp(u,ke[u][i].S);
        fort(j, 1, 18)
        {
            par[v][j].F = par[par[v][j-1].F][j-1].F;
            par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
        }
        dfs(v, u);
    }
}

pii lca(ll u, ll v)
{
    pii p;
    p.S = 1ll* maxc * maxc;
    if( h[u] > h[v])
        swap(u, v);
    ll diff = h[v] - h[u];
    ford(i, 18, 0)
        if((diff >> i) & 1)
        {
            p.S = min(p.S, par[v][i].S);
            v = par[v][i].F;

        }
    if(v == u) return mp(u, p.S);
    ford(i, 18, 0)
        if(par[u][i].F != par[v][i].F)
        {
            p.S = min(p.S, min(par[v][i].S, par[u][i].S));
            v = par[v][i].F;
            u = par[u][i].F;
        }
    return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
}

void work()
{
    make_tree();
    h[1] = 1;
    dfs(1, 0);
    fort(i, 1, m)
        if(!dd[i])
        {
            pii l = lca(ed[i].u, ed[i].v);
            res += max(0ll, l.S - ed[i].w);
        }
    cout << res;
}


int main()
{
    fast
  //  freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    work();
    return 0;
}

Cowboy

Chủ đề: DFS, Đồ thị, Kruskal, LCA, Phương pháp Mức độ:

AZNET – spoj

December 4, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Code:

Const   inp = '';
        out = '';
        maxn = 10001;
        maxm = 100001;
 
Var     n,m,ntest,min,max,k,res     :       longint;
        x,y,id :       array [1..2,1..maxm] of longint;
        lab :       array [1..2,1..maxn] of longint;
        sl      :   array [1..2] of longint;
        a,b :       array [0..maxn] of longint;
{***************************************************************************}
function getroot(t,u : longint) : longint;
  begin
      while lab[t,u] > 0 do u := lab[t,u];
      exit(u);
  end;
{***************************************************************************}
procedure union(t,r1,r2 : longint);
var x : longint;
  begin
      x := lab[t,r1]+lab[t,r2];
      if lab[t,r1] > lab[t,r2] then
       begin
           lab[t,r1] := r2;
           lab[t,r2] := x;
       end
      else begin
               lab[t,r2] := r1;
               lab[t,r1] := x;
           end;
  end;
{****************************************************************************}
procedure main;
var i,j,dem,u,v,r1,r2,r3,r4 : longint;
  begin
      for i := 1 to n do
        begin
            lab[1,i] := -1;
            lab[2,i] := -1;
        end;
      max := 0;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then
             begin
                 inc(max);
                 union(1,r1,r2);
             end;
        end;
      min := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                inc(min);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(2,u); r2 := getroot(2,v);
            if r1 <> r2 then
              begin
                  inc(min);
                  union(2,r1,r2);
              end;
        end;
      min := n-1-min;
      res := maxlongint;
      for i := min to max do
        if a[i]+b[n-1-i] < res then
          begin
              res := a[i]+b[n-1-i];
              k := i;
          end;
      for i := 1 to n do
        begin
            lab[1,i] := -1; lab[2,i] := -1;
        end;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then union(1,r1,r2);
        end;
      dem := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                write(id[2,i],' ');
                inc(dem);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      if dem < n-1-k then
        begin
           for i := 1 to sl[2] do
            begin
                u := x[2,i]; v := y[2,i];
                r1 := getroot(2,u); r2 := getroot(2,v);
                if r1 <> r2 then
                 begin
                     inc(dem);
                     write(id[2,i],' ');
                     union(2,r1,r2);
                     if dem=n-1-k then break;
                 end;
            end;
        end;
      for i := 1 to sl[1] do
        begin
          u := x[1,i]; v := y[1,i];
          r1 := getroot(2,u); r2 := getroot(2,v);
          if r1 <> r2 then
            begin
                write(id[1,i],' ');
                union(2,r1,r2);
            end;
        end;
      writeln;
  end;
{***************************************************************************}
procedure nhap;
var i,j,u,v,k : longint;
  begin
      assign(input,inp); reset(input);
      assign(output,out); rewrite(output);
      readln(ntest);
      while ntest > 0 do
       begin
           dec(ntest);
           readln(n,m);
           for i := 1 to n-1 do read(a[i]);
           for i := 1 to n-1 do read(b[i]);
           sl[1] := 0; sl[2] := 0;
           for i := 1 to m do
             begin
                 readln(u,v,k);
                 inc(sl[k]);
                 x[k,sl[k]] := u; y[k,sl[k]] := v;
                 id[k,sl[k]] := i;
             end;
           main;
       end;
  end;
{****************************************************************************}
begin
     nhap;
end.
Chủ đề: Đồ thị, Kruskal

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 độ: ,

NKCITY – SPOJ

May 24, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/NKCITY/

Thuật toán:

  • Giải bài này có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal đều được.
  • Các bạn có thể tham khảo cả 2 cách làm ở bên dưới.

Code:

Kruskal

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
        maxm    =10000;

type    data    =record
                u, v, c :longint;
                end;

var     f       :Text;
        n, m    :longint;
        Edges   :array[1..maxm] of Data;
        b       :Array[1..maxm] of longint;
        Father  :Array[1..maxn] of longint;
        res     :longint;
procedure nhap;
var     i, u, v, c :longint;
begin
        assign(f, fi);
        reset(f);
        readln(f, n, m);
        for i:=1 to m do
                begin
                        readln(f, u, v, c);
                        Edges[i].u:=u;
                        Edges[i].v:=v;
                        Edges[i].c:=c;
                end;
        close(f);
end;

Procedure init;
var     i :longint;
begin
        for i:=1 to m do b[i]:=i;
        for i:=1 to n do father[i]:=-1;
        res:=-1;
end;

procedure QS(l,r:longint);
var     i, j, x, tg     :longint;
begin
        i:=l;
        j:=r;
        x:=edges[b[ (l+r) div 2] ].c;
        repeat
                while Edges[b[i]].c < x do inc(i);
                while Edges[b[j]].c > x do dec(j);
                if i<=j then
                        begin
                                tg:=b[i];
                                b[i]:=b[j];
                                b[j]:=tg;
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l0 do t:=father[t];
        exit(t);
end;

procedure union(i, j:longint);
var     x :longint;
begin
        x:=father[i]+father[j];
        if father[i]>father[j] then
                begin
                        father[i]:=j;
                        father[j]:=x;
                end
        else    begin
                        father[j]:=i;
                        father[i]:=x;
                end;
end;

procedure Kruskal;
var     i, u,v, c, r1, r2 :longint;
begin
        init;
        QS(1,m);
        for i:=1 to m do
                begin
                        u:=Edges[b[i]].u;
                        v:=Edges[b[i]].v;
                        c:=Edges[b[i]].c;
                        r1:=find(u);
                        r2:=find(v);
                        if r1<>r2 then
                                begin
                                        union(r1,r2);
                                        res:=max(res,c);
                                end;
                end;
end;

procedure xuat;
begin
        assign(f, fo);
        rewrite(f);
        writeln(f, res);
        close(f);
end;

BEGIN
        nhap;
        Kruskal;
        xuat;
END.

Prim

const   fi='';
        fo='';
        maxn=1000;
        maxc=trunc(1e9);
var     d:array[1..maxn] of longint;
        i,j,n,m,res:longint;
        u,v,t:longint;
        cx:array[1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of longint;
procedure init;
begin
    for i:=1 to n do d[i]:=maxc;
    d[1]:=0;
    fillchar(cx,sizeof(cx),true);
end;
procedure prim;
var     min,u:longint;
begin
        repeat
                min:=maxc;u:=0;
                for i:=1 to n do
                        if cx[i] then
                        if d[i]res then res:=d[u];
                for v:=1 to n do
                        if cx[v] then
                                if d[v]>c[u,v] then
                                        begin
                                            d[v]:=c[u,v];
                                        end;
        until false;
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    readln(n,m);
    for i:=1 to n do
        for j:=1 to n do
                if i<>j then c[i,j]:=maxc else c[i,j]:=0;
    for i:=1 to m do
        begin
            readln(u,v,t);
            c[u,v]:=t;
            c[v,u]:=t;
        end;
    init;
    prim;
    writeln(res);
    close(input);close(output);
end.
Chủ đề: Kruskal, Prim, SPOJ Mức độ: , ,