8
27
2013
0

【BZOJ1295】【SCOI2009】最长距离【DFS】

数据范围很小,用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.
Category: dfs | Tags:
8
27
2013
0

【BZOJ1565】【NOI2009】植物大战僵尸【最大流+拓扑序】

裸的最大权闭合图,但是预处理比较恶心,我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.
Category: 最大流 | Tags:
8
27
2013
0

【BZOJ1787】【Ahoi2008】Meet 紧急集合【倍增(最近公共祖先)】

如果只有两个点,我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不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.
Category: 倍增 | Tags:
8
20
2013
0

【BZOJ1221】【HNOI2001】软件开发【费用流】

把每天拆成两个,分别记为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.
Category: 费用流 | Tags:
8
20
2013
0

【BZOJ1088】【SCOI2005】扫雷Mine【DP】

对于每个第二行的点与其有关的只有第一行的三个点,给左边的赋权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.
Category: DP | Tags:
8
18
2013
0

【BZOJ1022】【SHOI2008】小约翰的游戏John【博弈论】

题解详见小礼物的大神的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.
Category: 博弈论 | Tags:
8
18
2013
0

【BZOJ1083】【SCOI2005】繁忙的都市【最小生成树】

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



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.
Category: 最小生成树 | Tags:
8
17
2013
0

【BZOJ1003】【ZJOI2006】物流运输trans【最短路+DP】

以天为状态,则f[i]=min(dj[1,i]*i,dj[j,i]*(i-j+1)+k+f[j-1](2<=j<=i)),dj[i,j]表示第i天到第j天均走同样的路线时的最短路。不需要初始化,在过程中要用到位运算来降低时间复杂度,详细见代码。

 



program p1003;
	type
		bian=record
			next,point,w:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,two,d:array[1..30] of longint;
		x,f:array[0..200] of int64;
		len,i,j,n,m,k,e,q,k1,k2,k3,maxn: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;
	function min(k1,k2:int64):int64;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findmin:longint;
		var
			i,j,k:longint;
		begin
			k:=maxlongint; j:=0;
			for i:=1 to m do
				if (d[i]<k) and (d[i]<>-1) then begin
					k:=d[i];
					j:=i;
				end;
			exit(j);
		end;
	procedure push(k1,k2:longint);
		var
			i,j:longint;
		begin
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if (b[i].w+d[k1]<d[j]) and (k2 and two[j]=0) then 
					d[j]:=b[i].w+d[k1];
				i:=b[i].next;
			end;
			d[k1]:=-1;
		end;
	function dj(k:longint):longint;
		var
			i,j,now:longint;
		begin
			fillchar(d,sizeof(d),$3f);
			d[1]:=0;
			for i:=1 to m do begin
				now:=findmin;
				if now=m then exit(d[m]);
				push(now,k);
			end;
		end;
	begin
		readln(n,m,k,e);
		len:=0;
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		for i:=1 to e do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
		end;
		two[1]:=1;
		for i:=2 to m do
			two[i]:=two[i-1]*2;
		readln(q);
		fillchar(x,sizeof(x),0);
		for i:=1 to q do begin
			readln(k1,k2,k3);
			for j:=k2 to k3 do
				x[j]:=x[j] or two[k1];
		end;
		fillchar(f,sizeof(f),$3f);
		maxn:=f[1];
		f[0]:=0;
		for i:=1 to n do begin
			k1:=x[i];
			for j:=i downto 2 do begin
				k2:=dj(k1);
				if k2<>maxn then begin
					f[i]:=min(f[i],k2*(i-j+1)+k+f[j-1]);
					k1:=k1 or x[j-1];
				end else break;
			end;
			k2:=dj(k1);
			if k2<>maxn then f[i]:=min(f[i],k2*i);
		end;
		writeln(f[n]);
	end.
Category: DP | Tags:
8
4
2013
0

【BZOJ2662】【BeiJing wc2012】冻结【分层图+最短路】

类似于2763,不过层与层之间的边权要改为原边权的一半。我直接改了这个细节贴2763的代码了。

program p2662;
	type
		bian=record
			next,point,w:longint;
		end;
		heap=record
			dis,point:longint;
		end;
	var
		p,d:array[1..200000] of longint;
		x:array[1..200000] of heap;
		b:array[1..1500000] of bian;
		ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
		now:heap;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].w:=k3;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function minn(k1,k2:longint):longint;
		begin
			if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(minn(k1,minn(k2,k3)));
		end;
	procedure press(k:longint);
		var
			i:longint;
			j:heap;
		begin
			i:=min(k,k*2,k*2+1);
			if i=k then exit;
			j:=x[k]; x[k]:=x[i]; x[i]:=j;
			press(i);
		end;
	procedure find(k:longint);
		var
			i:heap;
		begin
                        if k=1 then exit;
			if x[k].dis<x[k div 2].dis then begin
				i:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=i;
				find(k div 2);
			end;
		end;
	procedure push(k:heap);
		var
			i,j:longint;
		begin
			i:=p[k.point];
			while i<>0 do begin
				j:=b[i].point;
				if k.dis+b[i].w<d[j] then begin
					d[j]:=k.dis+b[i].w;
					inc(len);
					x[len].point:=j;
					x[len].dis:=d[j];
					find(len);
				end;
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m,k);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,k3 div 2);
				ade(j*n+k2,j*n+k1+n,k3 div 2);
				add(j*n+n+k1,j*n+n+k2,k3);
			end;
		end;
		fillchar(d,sizeof(d),$3f);
		fillchar(x,sizeof(x),$7f);
		maxn:=x[1].dis;
		s:=1; t:=n;
		len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
		while len>0 do begin
			dec(len);
			now:=x[1];
			if len>0 then begin
				x[1]:=x[len+1];
				x[len+1].dis:=maxn;
				press(1);
			end;
			push(now);
		end;
		ans:=maxlongint;
		for i:=0 to k do
			if d[i*n+t]<ans then ans:=d[i*n+t];
		writeln(ans);
	end.
Category: 分层图 | Tags:
8
4
2013
0

【BZOJ2763】【JLOI2011】飞行路线【分层图+最短路】

把原图复制K+1遍,如果原来点I,J之间有边就在第P层的I向P+1层J连一条有向边,同理,第P层的点J向P+1层I连一条有向边。以第一层S为原点做最短路,答案就是所有层T点距离的最小值。应注意SPFA会T,应该用DJ+HEAP。

program p2736;
	type
		bian=record
			next,point,w:longint;
		end;
		heap=record
			dis,point:longint;
		end;
	var
		p,d:array[1..200000] of longint;
                x:array[1..200000] of heap;
		b:array[1..3000000] of bian;
		ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
		now:heap;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].w:=k3;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function minn(k1,k2:longint):longint;
		begin
			if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(minn(k1,minn(k2,k3)));
		end;
	procedure press(k:longint);
		var
			i:longint;
			j:heap;
		begin
			i:=min(k,k*2,k*2+1);
			if i=k then exit;
			j:=x[k]; x[k]:=x[i]; x[i]:=j;
			press(i);
		end;
	procedure find(k:longint);
		var
			i:heap;
		begin
                        if k=1 then exit;
			if x[k].dis<x[k div 2].dis then begin
				i:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=i;
				find(k div 2);
			end;
		end;
	procedure push(k:heap);
		var
			i,j:longint;
		begin
			i:=p[k.point];
			while i<>0 do begin
				j:=b[i].point;
				if k.dis+b[i].w<d[j] then begin
					d[j]:=k.dis+b[i].w;
					inc(len);
					x[len].point:=j;
					x[len].dis:=d[j];
					find(len);
				end;
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m,k);
		readln(s,t);
		inc(s); inc(t);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			inc(k1); inc(k2);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,0);
				ade(j*n+k2,j*n+k1+n,0);
				add(j*n+n+k1,j*n+n+k2,k3);
			end;
		end;
		fillchar(d,sizeof(d),$3f);
		fillchar(x,sizeof(x),$7f);
		maxn:=x[1].dis;
		len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
		while len>0 do begin
			dec(len);
			now:=x[1];
			if len>0 then begin
				x[1]:=x[len+1];
				x[len+1].dis:=maxn;
				press(1);
			end;
			push(now);
		end;
		ans:=maxlongint;
		for i:=0 to k do
			if d[i*n+t]<ans then ans:=d[i*n+t];
		writeln(ans);
	end.
Category: 分层图 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com