记录编号	39105	评测结果	AAAAAAAAAT
题目名称	危险游戏	最终得分	90
用户昵称	IMSL77	是否通过	未通过
代码语言	Pascal	运行时间	1.075 s
提交时间	2012-07-04 17:39:38	内存使用	8.38 MiB

program main;
type
  integer=longint;
  edges=record st,en:integer; l:integer; ontree:boolean; end;
const
  maxn=10010;
  maxm=100100;
var
  n,m,q:integer;
  sum:integer;
  tot:integer;
  edge:array[0..maxm] of edges;
  c:array[1..maxm] of integer;
  father:array[1..maxn] of integer;
  ver:array[1..maxn] of integer;
  st,en,next,tick:array[1..maxm shl 2] of integer;
  mark:array[1..maxn] of boolean;
  Que:array[1..maxn] of integer;
  bef,pre:array[1..maxn] of integer;

  procedure Fopen;
  begin
    assign(input,'tubea.in');
    reset(input);
    assign(output,'tubea.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(n,m);
    for i:=1 to m do
    begin
      readln(edge[i].st,edge[i].en,edge[i].l);
      edge[i].ontree:=false;
    end;
    edge[0].l:=-1;
  end;

  procedure QSort(l,r:integer);
  var
    i,j:integer;
    t,x:integer;
  begin
    i:=l; j:=r;
    x:=edge[c[(l+r) shr 1]].l;
    repeat
      while edge[c[i]].l<x do inc(i);
      while edge[c[j]].l>x do dec(j);
      if i<=j then
      begin
        t:=c[i]; c[i]:=c[j]; c[j]:=t;
        inc(i); dec(j);
      end;
    until i>j;
    if l<j then QSort(l,j);
    if i<r then QSort(i,r);
  end;

  function getfather(x:integer):integer;
  begin
    if father[x]=x then exit(x);
    father[x]:=getfather(father[x]);
    exit(father[x]);
  end;

  procedure Kruskal;
  var
    i:integer;
    fx,fy:integer;
  begin
    for i:=1 to m do c[i]:=i;
    QSort(1,m);
    sum:=0;
    for i:=1 to n do father[i]:=i;
    for i:=1 to m do
    begin
      fx:=getfather(edge[c[i]].st);
      fy:=getfather(edge[c[i]].en);
      if fx<>fy then
      begin
        father[fx]:=fy;
        edge[c[i]].ontree:=true;
        sum:=sum+edge[c[i]].l;
      end;
    end;
    writeln(sum);
  end;

  procedure addedge(u,v,c:integer);
  begin
    inc(tot);
    en[tot]:=v; next[tot]:=ver[u]; ver[u]:=tot;
    tick[tot]:=c; st[tot]:=u;
    inc(tot);
    en[tot]:=u; next[tot]:=ver[v]; ver[v]:=tot;
    tick[tot]:=c; st[tot]:=v;
  end;

  procedure SetGraph;
  var
    i:integer;
  begin
    fillchar(ver,sizeof(ver),0);
    fillchar(next,sizeof(next),0);
    tot:=1;
    for i:=1 to m do
      if edge[i].ontree then addedge(edge[i].st,edge[i].en,i);
  end;

  procedure BFS(s,t:integer);
  var
    head,tail:integer;
    k,u,v:integer;
  begin
    fillchar(mark,sizeof(mark),true);
    mark[s]:=false;
    head:=1; tail:=2;
    Que[1]:=s;
    while head<tail do
    begin
      u:=Que[head];
      k:=ver[u];
      while k>0 do
      begin
        v:=en[k];
        if mark[v] then
        begin
          mark[v]:=false;
          bef[v]:=u;
          pre[v]:=k;
          if v=t then exit;
          Que[tail]:=v;
          inc(tail);
        end;
        k:=next[k];
      end;
      inc(head);
    end;
  end;

  procedure deleteedge(u,p:integer);
  var
    k,fa:integer;
  begin
    k:=ver[u];
    if k=p then
    begin
      ver[u]:=next[k];
      exit;
    end;
    fa:=k; k:=next[k];
    while k<>p do
    begin
      k:=next[k];
      fa:=next[fa];
    end;
    next[fa]:=next[k];
  end;

  procedure Query;
  var
    i:integer;
    u,v,w:integer;
    max,max2:integer;
  begin
    readln(q);
    for i:=1 to q do
    begin
      readln(u,w);
      if edge[u].ontree then
      begin
        sum:=sum-edge[u].l+w;
        edge[u].l:=w;
        writeln(sum);
        continue;
      end;
      edge[u].l:=w;
      BFS(edge[u].st,edge[u].en);
      v:=edge[u].en; max:=0;
      while v<>edge[u].st do
      begin
        if edge[tick[pre[v]]].l>edge[max].l then
        begin
          max:=tick[pre[v]];
          max2:=pre[v];
        end;
        v:=bef[v];
      end;
      if edge[max].l>edge[u].l then
      begin
        sum:=sum-edge[max].l+edge[u].l;
        edge[max].ontree:=false;
        edge[u].ontree:=true;
        deleteedge(st[max2],max2);
        deleteedge(en[max2],max2 xor 1);
        addedge(edge[u].st,edge[u].en,u);
      end;
      writeln(sum);
    end;
  end;

begin
  Fopen;
  Init;
  Kruskal;
  SetGraph;
  Query;
  Fclose;
end.