jiry_2's Blog

水题，加一个点最小生成树

program p01;
    var
        b:array[0..300,0..300] of longint;
        d:array[0..300] of longint;
        n,i,j,tot:longint;
    function findmin:longint;
        var
            i,j,k:longint;
        begin
            j:=0; k:=maxlongint;
            for i:=0 to n do
                if (k>d[i]) and (d[i]<>-1) then begin
                    j:=i; k:=d[i];
                end;
            exit(j);
        end;
    procedure change(k:longint);
        var
            i,j:longint;
        begin
            for i:=0 to n do
                if b[k,i]<d[i] then d[i]:=b[k,i];
            d[k]:=-1;
        end;
    begin
        readln(n);
        for i:=1 to n do begin
            read(b[0,i]);
            b[i,0]:=b[0,i];
        end;
        for i:=1 to n do
            for j:=1 to n do
                read(b[i,j]);
        fillchar(d,sizeof(d),$3f);
        d[0]:=0; tot:=0;
        for i:=0 to n do begin
            j:=findmin;
            tot:=tot+d[j];
            change(j);
        end;
        writeln(tot);
    end.       

我是用二分边权然后判联通做的。但是貌似直接用最小生成树就可以。。

program p1083;
	type
		bian=record
			point,next,w,f:longint;
		end;
	var
		b:array[1..50000] of bian;
		p,d:array[1..400] of longint;
		pd:array[1..400] of boolean;
		x:array[1..50000] of longint;
		l,r,mid,ans,i,j,n,m,k1,k2,k3,len:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	procedure qsort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[i];
			while i<j do begin
				while (i<j) and (b[x[0]].w<=b[x[j]].w) do dec(j);
				if (i<j) then x[i]:=x[j];
				while (i<j) and (b[x[0]].w>b[x[i]].w) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then qsort(first,i-1);
			if j<en-1 then qsort(i+1,en);
		end;
	procedure find(k1,k2:longint);
		var
			i,j:longint;
		begin
			pd[k1]:=true;
			i:=p[k1];
			while i>0 do begin
				j:=b[i].point;
				if (b[i].f<=k2) and (pd[j]=false) then
					find(j,k2);
				i:=b[i].next;
			end;
		end;
	function charge:boolean;
		var
			i:longint;
		begin
			for i:=1 to n do
				if pd[i]=false then exit(false);
			exit(true);
		end;
	begin
		readln(n,m);
		len:=0;
		if n=1 then begin
			writeln(0,' ',0);
			exit;
		end;
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
		end;
		for i:=1 to len do
			x[i]:=i;
		qsort(1,len);
		for i:=1 to len do
			b[x[i]].f:=i;
		l:=1; r:=len+1;
		while l<r do begin
			mid:=(l+r) div 2;
			fillchar(pd,sizeof(pd),false);
			find(1,mid);
			if charge then begin
				r:=mid;
				ans:=mid;
			end else l:=mid+1;
		end;
		writeln(n-1,' ',b[x[ans]].w);
	end.