jiry_2's Blog

数学题，略蛋疼。可以证明最优的方案一定是先沿着较长边走，然后再走较短边。这样的话答案就是1+n+C¹n+C²n+1+...+C^mn+m。然后由于答案是取模一个指数num，那么对于一个组合a/b，由费马小定理a/b mod num=a*b^(num-2) mod num。那么答案就可以用快速幂求得。这样时间复杂度就是mlogm，由于m是较短边，那么m<=1000000，而由于快速幂太慢，我开始T了好久，后来用位运算瞎搞搞A了。

program p3260;
	const
		num=1000000007;
	var
		n,m,k1,k2,tot:int64;
		i,j:longint;
	function quick(k1,k2:int64):int64;
		var	
			k,i:int64;
		begin
			k:=k1; i:=1;
			while k2>0 do begin
				if k2 and 1>0 then
					i:=i*k mod num;
				k:=k*k mod num; k2:=k2 shr 1;
			end;
			exit(i);
		end;
	begin
		readln(n,m);
		if n<m then begin k1:=m; m:=n; n:=k1; end; n:=n mod num;
		tot:=n+1; k1:=1; k2:=1;
		for i:=1 to m do begin
			k1:=k1*i mod num;
			k2:=k2*(n+i) mod num;
			tot:=((tot+quick(k1,num-2)*k2) mod num);
		end;
		writeln(tot);
	end.

如果没有食人鱼的限制，那么K秒后的方案数就是邻接矩阵自乘K次后的B[S,E]，那么有了限制之后我们可以知道邻接矩阵一定以12个单位时间周期性变化。比如在第i个时刻第j个点上有鳄鱼。那么把第i-1时刻的矩阵中[1..n][j]置零，第i时刻的矩阵中[j][1..n]置零。很好想通。那么K/12的用快速幂。K%12的暴力求。

program p1898;
	const
		num=10000;
	type
		arr=array[1..50,1..50] of longint;
	var
		x:array[0..11] of arr;
		b,y,z:arr;
		f:array[1..20,0..4] of longint;
		n,i,j,m,s,e,k,k1,k2,nf:longint;
	function chen(k1,k2:arr):arr;
		var
			i,j,k:longint;
			k3:arr;
		begin
			fillchar(k3,sizeof(k3),0);
			for i:=1 to n do
				for j:=1 to n do
					for k:=1 to n do
						k3[i,j]:=(k1[i,k]*k2[k,j]+k3[i,j]) mod num;
			exit(k3);
		end;
	function quick(k1:arr;k2:longint):arr;
		var
			i,j:longint;
			k3:arr;
		begin
			if k2=0 then begin
				fillchar(k3,sizeof(k3),0);
				for i:=1 to n do
					k3[i,i]:=1;
				exit(k3);
			end;
			if k2=1 then exit(k1);
			k3:=quick(k1,k2 div 2);
			if k2 mod 2=0 then exit(chen(k3,k3));
			exit(chen(chen(k3,k3),k1));
		end;
	begin
		readln(n,m,s,e,k);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2);
			b[k1+1,k2+1]:=1;
			b[k2+1,k1+1]:=1;
		end;
		readln(nf);
		for i:=1 to nf do begin
			read(f[i,0]);
			for j:=1 to f[i,0] do begin
				read(f[i,j]);
				inc(f[i,j]);
			end;
		end;
		for i:=0 to 11 do
			x[i]:=b;
		for i:=1 to nf do
			for k1:=0 to 11 do begin
				for k2:=1 to n do
					x[k1,k2,f[i,(k1+1) mod f[i,0]+1]]:=0;
				for k2:=1 to n do
					x[k1,f[i,k1 mod f[i,0]+1],k2]:=0;
			end;
		z:=x[0];
		for i:=1 to 11 do
			z:=chen(z,x[i]);
		y:=quick(z,k div 12);
		for i:=0 to k mod 12-1 do
			y:=chen(y,x[i]);
		writeln(y[s+1,e+1]);
	end.

很容易就可以想到时间复杂度为nlog²n的算法。即用类似于求最近公共祖先的预处理。令f[i][j]为i的第2^j祖先。w[i][j]为i到f[i][j]路径不包括i的权值和。则可以得到递推式:f[i][j]=f[f[i,j-1]][j-1]，w[i][j]=w[f[i,j-1]][j-1]+w[i][j-1]。然后对于节点i，二分路径向上走多少层，如果可以二分得到其路径权值和s恰好相等则方案数加一，不要忘了只有节点i的情况。速度比较慢，存在复杂度为nlogn的算法，但是要用set或者treap，这对于pascal党太痛苦了，所以上述方法简单实用！

program p2783;
	type
		bian=record
			next,point:longint;
		end;
	var
		f,w:array[1..100000,0..25] of longint;
		d,x,p:array[0..100000] of longint;
		b:array[1..100000] of bian;
		l,r,mid,s,tot,len,n,i,j,k1,k2:longint;
		bo:boolean;
	procedure add(k1,k2:longint);
		begin
			inc(len);
			b[len].next:=p[k1];
			b[len].point:=k2;
			p[k1]:=len;
		end;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			f[k1,0]:=k2; d[k1]:=d[k2]+1;
			w[k1,0]:=x[k2];
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				dfs(j,k1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			for k:=1 to 30 do
				if 1 shl k>k2 then break;
			dec(k); j:=0;
			for i:=k downto 0 do
				if k2 and (1 shl i)>0 then begin
					j:=j+w[k1,i];
					k1:=f[k1,i];
				end;
			exit(j);
		end;
	begin
		readln(n,s);
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to n do
			read(x[i]);
		x[0]:=0;
		len:=0;
		for j:=1 to n-1 do begin
			readln(k1,k2);
			add(k1,k2);
		end;
		fillchar(d,sizeof(d),0);
		fillchar(f,sizeof(f),0);
		dfs(1,0);
		bo:=true; j:=0;
		while bo=true do begin
			inc(j);
			bo:=false;
			for i:=1 to n do begin
				if 1 shl j>=d[i] then continue;
				f[i,j]:=f[f[i,j-1],j-1];
				bo:=true;
				w[i,j]:=w[f[i,j-1],j-1]+w[i,j-1];
			end;
		end;
		tot:=0;
		for i:=1 to n do begin
			if x[i]=s then begin
				inc(tot);
				continue;
			end;
			l:=1; r:=d[i]; 
			while l<r do begin
				mid:=(l+r) div 2;
				k1:=go_up(i,mid)+x[i];
				if k1>s then r:=mid
					else if k1<s then l:=mid+1
						else begin
							inc(tot);
							break;
						end;
			end;
		end;
		writeln(tot);
	end.

数据范围很小，用DFS来个时空复杂度都是n2m2t乱搞搞就A掉了

program p1295;
	const
		h:array[1..4] of longint=(1,0,-1,0);
		s:array[1..4] of longint=(0,1,0,-1);
	var
		pd1:array[1..30,1..30,1..30,1..30,0..30] of boolean;
		pd2:array[1..30,1..30,1..30,1..30] of boolean;
		bo:array[1..30,1..30] of boolean;
		n,m,i,j,ii,jj,t:longint;
		ch:char;
		max:extended;
	procedure dfs(k1,k2,k3,k4,k5:longint);
		var
			i,j,a,b:longint;
		begin
			pd2[k1,k2,k3,k4]:=true;
			pd1[k1,k2,k3,k4,k5]:=true;
			for i:=1 to 4 do begin
				a:=k3+h[i]; b:=k4+s[i];
				if (a>0) and (a<=n) and (b>0) and (b<=m) then begin
					if (bo[a,b]=false) and (k5+1<=t) and (pd1[k1,k2,a,b,k5+1]=false) then begin
						pd1[k1,k2,a,b,k5+1]:=true;
						dfs(k1,k2,a,b,k5+1);
					end else if (bo[a,b]=true) and (pd1[k1,k2,a,b,k5]=false) then begin
						pd1[k1,k2,a,b,k5]:=true;
						dfs(k1,k2,a,b,k5);
					end;
				end;
			end;
		end;
	begin
		readln(n,m,t);
		fillchar(bo,sizeof(bo),true);
		fillchar(pd1,sizeof(pd1),false);
		fillchar(pd2,sizeof(pd2),false);
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='1' then bo[i,j]:=false;
			end;
			readln;
		end;
		for i:=1 to n do
			for j:=1 to m do
				if bo[i,j]=true then
					dfs(i,j,i,j,0)
				else if t>0 then dfs(i,j,i,j,1);
		max:=0;
		for i:=1 to n do
			for j:=1 to m do
				for ii:=1 to n do
					for jj:=1 to m do
						if (pd2[i,j,ii,jj]) and (sqrt(sqr(i-ii)+sqr(j-jj))>max) then
							max:=sqrt(sqr(i-ii)+sqr(j-jj));
		writeln(max:0:6);
	end.

裸的最大权闭合图，但是预处理比较恶心，我WA了好久。首先如果A保护B，那么就连一条A-->B的边，然后对这个图做拓扑序，把环给去掉（拓扑序算法结束后余下的点集便是环集），接下来对于每个换上的点作DFS，把被它保护的点和间接被它保护的点都去掉。然后对于余下的图进行网络流操作，见图如下：

1.如果A保护B则连一条B-->A流量为无穷大的边。

2.如果A的点权>0则连一条S-->A流量为A的点权的边。

3.如果A得点权<0则连一条A-->T流量为A的点权的绝对值的边。

以上操作的要求是AB均为没有被删去的点。然后跑一便最大流，最大流量为maxflow，令tot为所有点权为正的点的点权之和。则答案就是tot-maxflow

program p1565;
	const
		maxn=100000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		b:array[0..2000000] of bian;
		p,f,inw,dst:array[0..10000] of longint;
		x:array[1..10000] of longint;
		pd,bo:array[0..100000] of boolean;
		tot,len,i,j,n,m,k,k1,k2:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].f:=k3;
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	function bfs:boolean;
		var
			k1,k2,k3,now,head,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			pd[0]:=true; head:=1; now:=0; x[1]:=0; dst[0]:=0;
			while now<head do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					k1:=b[i].point;
					if (pd[k1]=false) and (b[i].f>0) and (bo[k1]=true)then begin
						pd[k1]:=true;
						dst[k1]:=dst[x[now]]+1;
						if k1=n+1 then exit(true);
						inc(head);
						x[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[n+1]);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=n+1) or (k2=0) then exit(k2);
			now:=p[k1];
			j:=0;
			while now>-1 do begin
				i:=b[now].point;
				if (b[now].f>0) and (dst[k1]=dst[i]-1) and (bo[i]=true)then begin
					k:=change(i,min(b[now].f,k2));
					k2:=k2-k;
					j:=j+k;
					b[now].f:=b[now].f-k;
					inc(b[now xor 1].f,k);
					if k2=0 then break;
				end;
				now:=b[now].next;
			end;
			if j=0 then dst[k1]:=-1;
			exit(j);
		end;
	function dinic:longint;
		var
			num,i:longint;
		begin
			num:=0;
			while bfs=true do begin
				num:=num+change(0,maxn);
			end;
			exit(num);
		end;
	procedure add(k1,k2,k3:longint);
		begin
			inc(inw[k1]);
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	procedure delete(k:longint);
		var
			i,j:longint;
		begin
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if i mod 2=1 then 
					dec(inw[j]);
				i:=b[i].next;
			end;
		end;
	function findmin:longint;
		var
			i,j:longint;
		begin
			for i:=1 to n do
				if (inw[i]=0) and (bo[i]=false) then
					exit(i);
			exit(0);
		end;
	procedure dfs(k:longint);
		var
			i,j:longint;
		begin
			pd[k]:=true;
			bo[k]:=false;
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if (pd[j]=false) and (i mod 2=1) then
					dfs(j);
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m);
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),-1);
		fillchar(dst,sizeof(dst),0);
		fillchar(inw,sizeof(inw),0);
		len:=-1;
		for i:=1 to n*m do begin
			read(f[i],k);
			for j:=1 to k do begin
				read(k1,k2);
				add(k1*m+k2+1,i,maxn);
			end;
		end;
		for i:=0 to n-1 do
			for j:=0 to m-2 do
				add(i*m+j+1,i*m+j+2,maxn);
		n:=n*m;
		fillchar(bo,sizeof(bo),false);
		while true do begin
			k:=findmin;
			if k=0 then break;
			bo[k]:=true;
			delete(k);
		end;
		tot:=0;
		fillchar(pd,sizeof(pd),false);
		for i:=1 to n do
			if (bo[i]=false) and (pd[i]=false) then 
				dfs(i);
		for i:=1 to n do begin
			if bo[i]=false then continue;
			if f[i]>0 then begin
				add(0,i,f[i]);
				tot:=tot+f[i];
			end else if f[i]<0 then
				add(i,n+1,-f[i]);
		end;
		bo[0]:=true; bo[n+1]:=true;
		tot:=tot-dinic;
		if tot<0 then tot:=0;
		writeln(tot);
	end.

如果只有两个点，我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不TLE，需要用倍增算法来确保NLOGN时间复杂度的在线查询。

program p1787;
	type
		bian=record
			point,next:longint;
		end;
	var
		b:array[1..1000005] of bian;
		p,d:array[0..500005] of longint;
		f:array[1..500005,1..30] of longint;
		len,n,m,i,j,k1,k2,k3,w1,w2,w3:longint;
		extra:array[1..3,1..2] of longint;
		bo:boolean;
	procedure ade(k1,k2:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2:longint);
		begin
			ade(k1,k2);
			ade(k2,k1);
		end;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			d[k1]:=d[k2]+1;
			f[k1,0]:=k2;
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if j<>k2 then dfs(j,k1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			for k:=0 to 30 do
				if 1 shl k>k2 then break;
			dec(k); if k<0 then exit(k1);
			j:=k1;
			for i:=0 to k do
				if k2 and (1 shl i)>0 then
					j:=f[j,i];
			exit(j);
		end;
	function fcf(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			if d[k1]>d[k2] then begin
				i:=k1; k1:=k2; k2:=i;
			end;
			k2:=go_up(k2,d[k2]-d[k1]);
			if k1=k2 then exit(k1);
			for k:=1 to 30 do
				if 1 shl k>=d[k1] then break;
			dec(k);
			for i:=k downto 0 do
				if f[k1,i]<>f[k2,i] then begin
					k1:=f[k1,i]; k2:=f[k2,i];
				end;
			exit(f[k1,0]);
		end;
	function pay(k1,k2,k3:longint):longint;
		begin
			exit(d[k1]-d[k3]+d[k2]-d[k3]);
		end;
	begin
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		readln(n,m);
		len:=0;
		for i:=1 to n-1 do begin
			readln(k1,k2);
			add(k1,k2);
		end;
		fillchar(d,sizeof(d),0);
		fillchar(f,sizeof(f),0);
		d[0]:=0;
		dfs(1,0);
		j:=1; bo:=true;
		while bo=true do begin
			bo:=false;
			for i:=1 to n do begin
				if d[i]<=1 shl j then continue;
				f[i,j]:=f[f[i,j-1],j-1];
				bo:=true;
			end;
			inc(j);
		end;{
		for i:=0 to 3 do begin
			for j:=1 to n do
				write(f[j,i],' ');
			writeln;
		end;}
		for i:=1 to m do begin
			readln(k1,k2,k3);
			extra[1,1]:=fcf(k1,k2);
			extra[1,2]:=fcf(extra[1,1],k3);
			extra[2,1]:=fcf(k1,k3);
			extra[2,2]:=fcf(extra[2,1],k2);
			extra[3,1]:=fcf(k2,k3);
			extra[3,2]:=fcf(extra[3,1],k1);
			w1:=pay(k1,k2,extra[1,1])+pay(extra[1,1],k3,extra[1,2]);
			w2:=pay(k1,k3,extra[2,1])+pay(extra[2,1],k2,extra[2,2]);
			w3:=pay(k2,k3,extra[3,1])+pay(extra[3,1],k1,extra[3,2]);
			if w1<w2 then begin 
				k1:=extra[1,1]; k2:=w1;
			end else begin	
				k1:=extra[2,1]; k2:=w2;
			end;
			if k2>w3 then begin
				k1:=extra[3,1]; k2:=w3;
			end;
			{for j:=1 to 3 do
				writeln(extra[j,1],' ',extra[j,2]);
			writeln(w1,' ',w2,' ',w3);}
			writeln(k1,' ',k2);
		end;
	end.

把每天拆成两个，分别记为Xi，Yi，从S向Xi连一条流量为maxint，费用为f的边。从S向Yi连一条流量ni，费用为0的边。从Yi向Yi+1连一条流量maxint，费用为0的边（最开始做没连这个，直接连到X去，连了好多的边，所以一直TLE）。从Yi向Xi+a连一条流量为maxint，费用为fa的边。从Yi向Xi+b连一条流量为maxint，费用为fb的边。从Xi向T连一条流量为k，费用为0的边。这个网络的最小费用最大流的费用就是答案。

program p1221;
	const
		maxn=100000000;
	type
		bian=record
			next,f,w,point:longint;
		end;
	var
		p,d,after:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		x:array[1..400000] of longint;
		b:array[0..1500000] of bian;
		len,i,j,n,a,c,f,fa,fb,k:longint;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k4;
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,-k3,0);
		end;
	function spfa:boolean;
		var
			head,i,j,now:longint;
		begin
			fillchar(x,sizeof(x),0);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			fillchar(after,sizeof(after),-1);
			x[1]:=0; head:=1; now:=0; pd[0]:=true; d[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;{
					writeln(b[i].f,' ',b[i].w+d[x[now]],' ',d[j]);
					readln;}
					if (b[i].f>0) and (b[i].w+d[x[now]]<d[j]) then begin
						d[j]:=b[i].w+d[x[now]];
						after[j]:=i;
						if pd[j]=false then begin
							pd[j]:=true;
							inc(head);
							x[head]:=j;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;{
			for i:=1 to n do
				write(d[i],' ');
			readln;}
			if after[n+1]>-1 then exit(true) else exit(false);
		end;
	function change:longint;
		var
			k,ans,tot,num,i,j:longint;
		begin
			i:=n+1; j:=after[i]; k:=maxn;
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			ans:=0; i:=n+1; j:=after[i];
			while j<>-1 do begin
				ans:=ans+k*b[j].w;
				dec(b[j].f,k);
				inc(b[j xor 1].f,k);
				i:=b[j xor 1].point;
				j:=after[i];
			end;{
			writeln(k,' ',ans);
		readln;	}
			exit(ans);
		end;
	function dinic:longint;
		var
			ans:longint;
		begin
			ans:=0;
			while spfa do
				ans:=ans+change;
			exit(ans);
		end;
	begin
		readln(n,a,c,f,fa,fb);
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			add(0,i,f,maxn);
		for i:=1 to n-1 do
			add(n+i,n+i+1,0,maxn);
		for i:=1 to n-a-1 do
			add(n+i,i+a+1,fa,maxn);
		for i:=1 to n-c-1 do
			add(n+i,i+c+1,fb,maxn);
		for i:=1 to n do begin
			read(k);
			add(i,n*2+1,0,k);
			add(0,n+i,0,k);
		end;
		n:=n*2;
		writeln(dinic);
		{readln;
		readln;}
	end.

对于每个第二行的点与其有关的只有第一行的三个点，给左边的赋权1，中间的赋权2，右边的赋权4，那么对于每个点都有8个情况，分别对应0--7.而这个是没后效性的，可以用动规解，不多说，看代码。话说动规的代码真的好短。

program p1088;
	var
		x:array[0..20000,0..7] of int64;
		y:array[1..20000] of longint;
		i,j,n:longint;
	begin
		readln(n);
		for i:=1 to n do
			read(y[i]);
		fillchar(x,sizeof(x),0);
		x[0,0]:=1;
		x[0,4]:=1;
		for i:=1 to n-1 do
			if y[i]=0 then
				x[i,0]:=x[i-1,0]+x[i-1,1]
			else if y[i]=1 then begin
				x[i,1]:=x[i-1,2]+x[i-1,3];
				x[i,2]:=x[i-1,4]+x[i-1,5];
				x[i,4]:=x[i-1,0]+x[i-1,1];
			end else if y[i]=2 then begin
				x[i,3]:=x[i-1,6]+x[i-1,7];
				x[i,6]:=x[i-1,4]+x[i-1,5];
				x[i,5]:=x[i-1,2]+x[i-1,3];
			end else if y[i]=3 then 
				x[i,7]:=x[i-1,6]+x[i-1,7];
		if y[n]=0 then writeln(x[n-1,0]+x[n-1,1])
			else if y[n]=1 then writeln(x[n-1,2]+x[n-1,3]+x[n-1,4]+x[n-1,5])
				else if y[n]=2 then writeln(x[n-1,6]+x[n-1,7]);
	end.

题解详见小礼物的大神的BLOG，弱渣就不说了。。。http://dzy493941464.is-programmer.com/posts/39629.html

program p1022;
	var
		t,n,i,ans,k,j,k1,k2:longint;
		bo:boolean;
	begin
		read(t);
		for k:=1 to t do begin
			read(n);
			ans:=0; k2:=0;
			for i:=1 to n do begin
				read(k1);
				if k1>1 then inc(k2);
				ans:=ans xor k1;
			end;
			if ((ans=0) and (k2>0)) or ((ans<>0) and (k2=0)) then writeln('Brother') else writeln('John');
		end;
	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.