9
17
2013
0

【BZOJ3251】树上三角形【倍增】

显然我们要求出每个询问两个点的最近公共祖先。然后我们可以求出其最短路径上的点数。显然,如果要不能构成三角形,那么上面的点权一定是按照大于斐波那契数列排列的,这样在55项左右就超过MAXLONGINT。所以大于等于55一定构成三角形。余下的反正是有50+的点直接SORT一下然后暴力即可。PASCAL的代码又一次又臭又长,居然垫底了。。QAQ

program p3251;
	type
		bian=record
			next,point:int64;
		end;
		arr=array[0..500] of int64;
	var
		f:array[1..111111,0..17] of int64;
		w,d,p:array[1..111111] of int64;
		b:array[1..111111] of bian;
		way:arr;
		len,i,j,q,n,k1,k2,k3:longint;
		ch:char;
		pd:boolean;
	procedure add(k1,k2:int64);
		begin
			inc(len); 
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure find(k1,k2:int64);
		var
			i,j:longint;
		begin
			d[k1]:=k2;
			i:=p[k1];
			while i<>0 do begin
				find(b[i].point,k2+1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:int64):int64;
		var
			i,j,k:longint;
		begin
			if k2=0 then exit(k1);
			for k:=0 to 17 do
				if 1 shl k>k2 then break;
			dec(k);
			for i:=0 to k do 
				if k2 and (1 shl i)>0 then k1:=f[k1,i];
			exit(k1);
		end;
	procedure sort(var x:arr;first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				while (i<j) and (w[x[j]]>=w[x[0]]) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (w[x[i]]<w[x[0]]) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(x,first,i-1);
			if i<en-1 then sort(x,i+1,en);
		end;	
	function answer(k1,k2:int64):char;
		var
			k,i,j,k3,k4,k5,l:longint;
		begin
			if d[k1]>d[k2] then begin
				i:=k1; k1:=k2; k2:=i;
			end;
			k3:=go_up(k2,d[k2]-d[k1]);
			for k:=0 to 17 do
				if 1 shl k>=d[k3] then break;
			dec(k);
			k4:=k1;
			if k3<>k4 then begin
				for i:=k downto 0 do
					if f[k3,i]<>f[k4,i] then begin
						k3:=f[k3,i];
						k4:=f[k4,i];
					end;
				k3:=f[k3,0];
			end;
			l:=d[k1]-d[k3]+d[k2]-d[k3]+1;
			if (l<3) then exit('N');
			if (l>=55) then exit('Y');
			l:=0;
			i:=k1; 
			while i<>k3 do begin
				inc(l); way[l]:=i; i:=f[i,0];
			end;
			i:=k2; inc(l); way[l]:=i;
			while i<>k3 do begin
				i:=f[i,0]; inc(l); way[l]:=i;
			end;
			sort(way,1,l);
			for i:=3 to l do
				if w[way[i-2]]+w[way[i-1]]>w[way[i]] then exit('Y');
			exit('N');
		end;
	begin
		readln(n,q);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		fillchar(f,sizeof(f),0);
		for i:=1 to n do
			read(w[i]);
		for i:=1 to n-1 do begin
			readln(k1,k2);
			f[k2,0]:=k1;
			add(k1,k2);
		end;
		find(1,1);
		for i:=1 to 17 do begin
			pd:=false;
			for j:=1 to n do
				if 1 shl i<d[j] then begin
					pd:=true;
					f[j,i]:=f[f[j,i-1],i-1];
				end;
			if pd=false then break;
		end;
		for i:=1 to q do begin
			readln(k1,k2,k3);
			if k1=0 then
				writeln(answer(k2,k3))
			else 
				w[k2]:=k3;
		end;
	end.
Category: 倍增 | Tags:
9
16
2013
0

【BZOJ1818】【Cqoi2010】内部白点【树状数组+离散化】

猥琐的树状数组,快排了三次,还要离散化。。代码又臭又长。原题等价于求所有水平数值线段的交点数目,把所有线段搞出来,分成水平的和竖直的,从上往下扫一遍,扫到横的就找一找它的左到右竖着的线段数。扫到竖着的上界就把它的横坐标插入,扫到下界就删掉。pascal党敲得翔都出来了,QAQ。

program p1818;
	type
		arr=array[0..1000000] of longint;
		line=record
			a,b:longint;
		end;
		point=record
			x,y,numx,numy:longint;
		end;
		point2=record
			y,a,b:longint;
		end;
	var
		p:array[1..1000000] of point;
		l:array[0..1000000] of point2;
		c:array[1..1000000] of longint;
		h,s:arr;
		x,y:array[0..1000000] of line;
		tot,len1,len2,i,j,n,len:longint;
	procedure sort1(first,en:longint);
		var
			i,j,t:longint;
		begin
			i:=first; j:=en; h[0]:=h[(i+j) div 2];
			while i<=j do begin
				while ((p[h[j]].x>p[h[0]].x) or ((p[h[j]].x=p[h[0]].x) and (p[h[j]].y>p[h[0]].y))) do dec(j);
				while ((p[h[i]].x<p[h[0]].x) or ((p[h[i]].x=p[h[0]].x) and (p[h[i]].y<p[h[0]].y))) do inc(i);
				if i<=j then begin
					t:=h[j]; h[j]:=h[i]; h[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort1(first,j);
			if i<en then sort1(i,en);
		end;
	procedure sort2(first,en:longint);
		var
			i,j,t:longint;
		begin
			i:=first; j:=en; s[0]:=s[(i+j) div 2];
			while i<=j do begin
				while ((p[s[j]].y>p[s[0]].y) or ((p[s[j]].y=p[s[0]].y) and (p[s[j]].x>p[s[0]].x))) do dec(j);
				while ((p[s[i]].y<p[s[0]].y) or ((p[s[i]].y=p[s[0]].y) and (p[s[i]].x<p[s[0]].x))) do inc(i);
				if i<=j then begin
					t:=s[j]; s[j]:=s[i]; s[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort2(first,j);
			if i<en then sort2(i,en);
		end;	
	procedure sort(first,en:longint);
		var
			i,j:longint;
			t:point2;
		begin
			i:=first; j:=en; l[0]:=l[(i+j) div 2];
			while i<=j do begin	
				while (l[j].y>l[0].y) do dec(j);
				while (l[i].y<l[0].y) do inc(i);
				if i<=j then begin 
					t:=l[j]; l[j]:=l[i]; l[i]:=t;
					inc(i); dec(j);
				end;
			end;
			if j>first then sort(first,j);
			if i<en then sort(i,en);
		end;
	function lowbit(k:longint):longint;
		begin
			exit(k and (-k));
		end;
	function find(k:longint):longint;
		var
			num,i:longint;
		begin
			num:=0;
			i:=k;
			while i>0 do begin
				num:=num+c[i];
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	procedure add(k1,k2:longint);
		var
			i:longint;
		begin
			i:=k1;
			while i<=n do begin
				inc(c[i],k2);
				i:=i+lowbit(i);
			end;
		end;
	begin
		readln(n);
		for i:=1 to n do
			readln(p[i].x,p[i].y);
		for i:=1 to n do begin
			h[i]:=i; s[i]:=i;
		end;
		sort1(1,n);
		sort2(1,n);
		j:=1; p[h[1]].numx:=1; len1:=0;
		for i:=2 to n do
			if p[h[i]].x=p[h[i-1]].x then begin
				p[h[i]].numx:=j;
				inc(len1);
				y[len1].a:=h[i-1]; y[len1].b:=h[i];
			end else begin
				inc(j);
				p[h[i]].numx:=j;
			end;
		j:=1; p[s[1]].numy:=1; len2:=0;
		for i:=2 to n do
			if p[s[i]].y=p[s[i-1]].y then begin
				p[s[i]].numy:=j;
				inc(len2);
				x[len2].a:=s[i-1]; x[len2].b:=s[i];
			end else begin
				inc(j);		
				p[s[i]].numy:=j;
			end;
		len:=0;
		for i:=1 to len2 do begin
			inc(len);
			l[len].y:=p[x[i].a].numy;
			l[len].a:=i;
			l[len].b:=1;
		end;
		for i:=1 to len1 do begin
			inc(len);
			l[len].y:=p[y[i].a].numy;
			l[len].a:=i;
			l[len].b:=2;
			inc(len);
			l[len].y:=p[y[i].b].numy;
			l[len].a:=i;
			l[len].b:=3;
		end;
		sort(1,len);
		tot:=0;
		fillchar(c,sizeof(c),0);
		for i:=1 to len do
			if l[i].b=1 then
				tot:=tot+find(p[x[l[i].a].b].numx-1)-find(p[x[l[i].a].a].numx)
			else if l[i].b=2 then 
				add(p[y[l[i].a].a].numx,1)
			else add(p[y[l[i].a].a].numx,-1);
		writeln(tot+n);
	end.
Category: 数据结构 | Tags:
9
14
2013
0

【BZOJ1493】【NOI2007】项链工厂【线段树】

第一次发现线段树可以写得那么高端洋气上档次。旋转和翻转忽略掉,对于每个询问把位置变为原来的位置即可。然后在线段树中记录区间的左界右界,合并的时候如果相等则减一(要注意在C中可能整个串都为同一个颜色,这就不能减)。然后便是裸的区间修改了,瞎搞搞,花了我两天多时间才A掉,细节太复杂,代码写得又臭又长。。。

 

program p1493;
	type
		result=record
			left,right,num:longint;
		end;
	var
		x:array[1..500000] of longint;
		num,left,right,bj:array[1..2000000] of longint;
		xz2,fz,xz,n,q,i,j,c,k1,k2,k3,k:longint;
		p,p1,p2:result;
		ch:char;
	procedure swap(var k1,k2:longint);
		var	
			i:longint;
		begin
			i:=k1; k1:=k2; k2:=i;
		end;
	procedure buildtree(len,l,r:longint);
		var
			i,j:longint;
		begin
			left[len]:=x[l]; right[len]:=x[r];
			if l<>r then begin
				buildtree(len*2,l,(l+r) shr 1);
				buildtree(len*2+1,(l+r) shr 1+1,r);
				num[len]:=num[len*2]+num[len*2+1];
				if left[len*2+1]=right[len*2] then 
					dec(num[len]);
			end else
				num[len]:=1;
		end;
	function changenum(k:longint):longint;
		var	
			i:longint;
		begin
			i:=(k+n-xz) mod n+1;
			if fz=1 then i:=(n+1-i) mod n+1;
			exit(i);
		end;
	function find(k1,k2,k3,k4,k5:longint):result;
		var
			k,i,j:result;
		begin
			if (k2>k5) or (k3<k4) then begin
				k.left:=0; k.right:=0; k.num:=0; exit(k);
			end;
			if bj[k1]<>0 then begin
				k.left:=bj[k1]; k.right:=bj[k1]; k.num:=1; exit(k);
			end;
			if (k2>=k4) and (k3<=k5) then begin
				k.left:=left[k1]; k.right:=right[k1]; k.num:=num[k1]; exit(k);
			end;
			i:=find(k1*2,k2,(k2+k3) shr 1,k4,k5);
			j:=find(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
			if i.num=0 then exit(j);
			if j.num=0 then exit(i);
			k.left:=i.left; k.right:=j.right; k.num:=i.num+j.num;
			if (i.right=j.left) and (i.right<>0) then dec(k.num);
			exit(k);
		end;
	procedure maintain(k1,k2,k3:longint);
		begin
			if bj[k1]<>0 then begin
				left[k1]:=bj[k1]; right[k1]:=bj[k1]; num[k1]:=1;
				exit;
			end;
			if k2=k3 then begin
				left[k1]:=x[k2]; right[k1]:=x[k2]; num[k1]:=1;
				exit;
			end;
			left[k1]:=left[k1*2]; right[k1]:=right[2*k1+1];
			num[k1]:=num[k1*2]+num[k1*2+1];
			if left[k1*2+1]=right[k1*2] then 
				dec(num[k1]);
		end;
	procedure changetotal(k1,k2,k3,k4,k5,k6:longint);
		begin
			if (k2>k5) or (k3<k4) then begin maintain(k1,k2,k3); exit; end;
			if (k2>=k4) and (k3<=k5) then
				bj[k1]:=k6
			else begin
				if bj[k1]>0 then begin 
					bj[k1*2]:=bj[k1]; bj[k1*2+1]:=bj[k1]; bj[k1]:=0;
				end;
				changetotal(k1*2,k2,(k2+k3) shr 1,k4,k5,k6);
				changetotal(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6);
			end;
			maintain(k1,k2,k3);
		end;
	function getchar:char;
		var	
			ch:char;
		begin
			read(ch);
			while (ch<'A') or (ch>'Z') do read(ch);
			exit(ch);
		end;
	begin
		readln(n,c);
		fillchar(bj,sizeof(bj),0);
		for i:=1 to n do
			read(x[i]);
		readln;
		buildtree(1,1,n);
		fz:=0; xz:=1;
		readln(q);
		for i:=1 to q do begin
			ch:=getchar;
			if ch='C' then begin
				read(ch);
				if ch='S' then begin
					readln(k1,k2);
					k1:=changenum(k1);
					k2:=changenum(k2);
					if fz=1 then swap(k1,k2);
					if k1>k2 then begin
						p1:=find(1,1,n,k1,n);
						p2:=find(1,1,n,1,k2);
						p.num:=p1.num+p2.num;
						p.left:=p1.left; p.right:=p2.right;
						if p1.right=p2.left then dec(p.num);
					end else begin
						p:=find(1,1,n,k1,k2);
					end;
					writeln(p.num);
				end else begin
					p:=find(1,1,n,1,n);
					if p.left=p.right then dec(p.num);
					if p.num=0 then p.num:=1;
					writeln(p.num);
					{for j:=1 to n do
						write(find(1,1,n,j,j).left,' ');
					readln;}
				end;
			end else if ch='P' then begin
				readln(k1,k2,k3);
				k1:=changenum(k1); k2:=changenum(k2);
				if fz=1 then swap(k1,k2);
				{WRITELN(K1,' ',K2);}
				if k1>k2 then begin
					changetotal(1,1,n,1,k2,k3);
					changetotal(1,1,n,k1,n,k3);
				end else
					changetotal(1,1,n,k1,k2,k3);
			end else if ch='S' then begin
				readln(k1,k2);
				k1:=changenum(k1); k2:=changenum(k2);
				if fz=1 then swap(k1,k2);
				{WRITELN(K1,' ',K2);}
				j:=find(1,1,n,k1,k1).left;
				k:=find(1,1,n,k2,k2).left;
				changetotal(1,1,n,k1,k1,k);
				changetotal(1,1,n,k2,k2,j);
			end else if ch='F' then begin
				fz:=(fz+1) mod 2;
				xz:=(n+1-xz) mod n+1;
			end else begin
				readln(k1);
				xz:=(xz+k1-1) mod n+1;
			end;
		end;
	end.
Category: 数据结构 | Tags:
9
9
2013
0

【BZOJ1061】【Noi2008】志愿者招募【费用流】

表示再一次没节操的看了题解。假设每一天的需求量是num[i],令num[0]=num[n+1]=0。那么如果对于1<=i<=n+1,如果num[i]-num[i-1]>0就由S向i连一条边,反之则连到T,流量为abs(num[i]-num[i-1]),费用为0。然后对于每类志愿者从a工作到b,费用为c,就从a向b+1连一条费用为c,流量为maxlongint的边。再由i+1向i连一条流量为maxlongint费用为0的边。求最小费用最大流即可。

program p1061;
	type
		bian=record
			next,point,w,f:int64;
		end;
	var
		b:array[1..500000] of bian;
		d,p,after,num:array[0..2000] of int64;
		x:array[1..100000] of longint;
		pd:array[0..2000] of boolean;
		len,n,m,i,j,k1,k2,k3:longint;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			b[len].w:=k4;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,0,-k4);
		end;
	function spfa:boolean;
		var
			i,j,now,head:longint;
		begin
			fillchar(after,sizeof(after),-1);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			x[1]:=0; pd[0]:=true; d[0]:=0; head:=1; now:=0;
			while now<head do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (b[i].f>0) and (d[x[now]]+b[i].w<d[j]) then begin
						d[j]:=d[x[now]]+b[i].w;
						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;
			if after[n+2]=-1 then exit(false) else exit(true);
		end;
	function min(k1,k2:int64):int64;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change:int64;
		var
			i,j,k,num:int64;
		begin
			k:=maxlongint*50000000; i:=n+2; j:=after[i];
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			num:=0; i:=n+2; j:=after[i];
			while j<>-1 do begin
				num:=num+k*b[j].w;
				inc(b[j xor 1].f,k);
				dec(b[j].f,k);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			exit(num);
		end;
	function dinic:int64;
		var
			num:int64;
		begin
			num:=0;
			while spfa=true do
				num:=num+change;
			exit(num);
		end;
	begin
		readln(n,m);
		fillchar(num,sizeof(num),0);
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),-1);
		len:=-1;
		for i:=1 to n do begin
			read(num[i]);
			if num[i]-num[i-1]>0 then 
				add(0,i,num[i]-num[i-1],0)
			else 
				add(i,n+2,num[i-1]-num[i],0);
		end;
		add(n+1,n+2,num[n],0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(k1,k2+1,maxlongint,k3);
		end;
		for i:=1 to n do
			add(i+1,i,maxlongint,0);
		writeln(dinic);
	end.
Category: 费用流 | Tags:
9
9
2013
0

【BZOJ1207】【HNOI2004】打鼹鼠【DP】

大水题,按照时间sort一下然后用类似于最长不下降子序列的算法水掉,虽然是m2的算法但是并不慢。

program p1207;
	type
		yanshu=record
			time,x,y:longint;
		end;
	var
		x:array[0..10000] of yanshu;
		f:array[0..10000] of longint;
		i,j,n,m:longint;
	procedure sort(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 (x[0].time<=x[j].time) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (x[0].time>x[i].time) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	begin
		readln(n,m);
		for i:=1 to m do
			readln(x[i].time,x[i].x,x[i].y);
		sort(1,m);
		for i:=1 to m do
			f[i]:=1;
		for i:=2 to m do
			for j:=1 to i-1 do
				if (f[j]+1>f[i]) and (abs(x[i].x-x[j].x)+abs(x[i].y-x[j].y)<=x[i].time-x[j].time) then
					f[i]:=f[j]+1;
		j:=0;
		for i:=1 to m do
			if f[i]>j then j:=f[i];
		writeln(j);
	end.
Category: DP | Tags:
9
9
2013
0

【BZOJ1601】【Usaco2008 Oct】灌水【最小生成树】

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

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

【BZOJ2875】【Noi2012】随机数生成器【矩乘】

就是裸的矩乘,要用快速乘(类似于快速幂)来防止爆INT64。还有要注意在最后的时候答案要先对M取模后再对G取模(坑了我好久)

program p2875;
	type
		arr=array[1..2,1..2] of int64;
	var
		j,k:longint;
		m,a,c,x,n,g,i:int64;
		k1,k2:arr;
	function quick2(k1,k2:int64):int64;
		var
			i,j,k,k3,k4:int64;
		begin
			k:=k2; i:=0;
			while k>0 do begin
				if k and 1>0 then 
					i:=(i+k1) mod m;
				k1:=k1*2 mod m; k:=k div 2;
			end;
			exit(i);
		end;
	function chen(k1,k2:arr):arr;
		var
			i,j,k:longint;
			k3:arr;
		begin
			fillchar(k3,sizeof(k3),0);
			for i:=1 to 2 do
				for j:=1 to 2 do
					for k:=1 to 2 do
						k3[i,j]:=(k3[i,j]+quick2(k1[i,k],k2[k,j]))mod m;
			exit(k3);
		end;
	function quick1(k1:arr;k2:int64):arr;
		var
			j,k:int64;
			i,k3,k4:arr;
		begin
			k:=k2-1; i:=k1;
			while k>0 do begin
				if k and 1>0 then 
					i:=chen(i,k1);
				k1:=chen(k1,k1); k:=k div 2;
			end;
			exit(i);
		end;
	begin
		readln(m,a,c,x,n,g);
		k1[1,1]:=a; k1[1,2]:=1;
		k1[2,1]:=0; k1[2,2]:=1;
		k1:=quick1(k1,n);
		i:=((quick2(k1[1,1],x)+quick2(k1[1,2],c)) mod m)mod g;
		writeln(i);
	end.

 

Category: 矩阵乘法 | Tags:
9
4
2013
0

【BZOJ1491】【NOI2007】社交网络【弗洛伊德】

两个弗洛伊德+乘法原理,第二个弗洛伊德居然写错了。。调了半天才调出来,QAQ

program p1491;
	var
		b,f:array[1..300,1..300] of int64;
		w:array[1..300] of extended;
		n,m,i,j,k1,k2,k3,k:longint;
	begin
		fillchar(f,sizeof(f),0);
		fillchar(b,sizeof(b),$3f);
		readln(n,m);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			if k3<b[k1,k2] then begin
				b[k1,k2]:=k3;
				b[k2,k1]:=k3;
				f[k1,k2]:=1;
				f[k2,k1]:=1;
			end;
		end;
		for k:=1 to n do 
			for i:=1 to n do
				for j:=1 to n do begin
					if (i=j) or (j=k) or (k=i) then continue;
					if b[i,k]+b[k,j]<b[i,j] then begin
						b[i,j]:=b[i,k]+b[k,j];
						f[i,j]:=f[i,k]*f[k,j];
					end else if b[i,k]+b[k,j]=b[i,j] then
						f[i,j]:=f[i,j]+f[i,k]*f[k,j];
				end;
		fillchar(w,sizeof(w),0);
		for k:=1 to n do
			for i:=1 to n do
				for j:=1 to n do
					if (i<>k) and (j<>k) and (b[i,k]+b[k,j]=b[i,j])and (i<>j)then
						w[k]:=w[k]+f[i,k]*f[k,j]/f[i,j];
		for i:=1 to n do
			writeln(w[i]:0:3);
	end.
Category: 最短路 | Tags:
9
4
2013
0

【BZOJ1497】【NOI2006】最大获利【最大流】

最大权闭合子图,最大流水掉

program p1497;
	const
		maxn=1000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		p,dst,x:array[0..100000] of longint;
		pd:array[0..60000] of boolean;
		b:array[0..1000000] of bian;
		tot,n,m,i,j,len,k1,k2,k3:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	function bfs:boolean;
		var
			head,now,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			x[1]:=0; pd[0]:=true; dst[0]:=0; head:=1; now:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) and (b[i].f>0) then begin
						dst[j]:=dst[x[now]]+1;
						pd[j]:=true;
						if j=n+m+1 then exit(true);
						inc(head);
						x[head]:=j;
					end;
					i:=b[i].next;
				end;
			end;
			exit(pd[n+m+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
			i,j,num,ans,k:longint;
		begin
			if (k1=n+m+1) or (k2=0) then exit(k2);
			ans:=0; i:=p[k1];
			while i<>-1 do begin
				j:=b[i].point;
				if (dst[j]=dst[k1]+1) and (b[i].f>0) then begin
					k:=change(j,min(k2,b[i].f));
					dec(k2,k); inc(ans,k);
					inc(b[i xor 1].f,k); dec(b[i].f,k);
					if k2=0 then break;
				end;
				i:=b[i].next;
			end;
			if ans=0 then dst[k1]:=-1;
			exit(ans);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do 
				num:=num+change(0,maxn);
			exit(num);
		end;
	begin
		readln(n,m);
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=1 to n do begin
			read(k1);
			add(i,n+m+1,k1);
		end;
		tot:=0;
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(n+i,k1,maxn);
			add(n+i,k2,maxn);
			add(0,n+i,k3);
			tot:=tot+k3;
		end;
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags:
9
4
2013
0

【BZOJ1041】【HAOI2008】圆上的整点【数学题】

瞎搞搞,用勾股定理的通式

program p1041;
	var
		len,tot,r,i,j:longint;
		x:array[1..10000,1..2] of longint;
	function find(k:longint):longint;
		var	
			i,j,a,b,num,c,d:longint;
			bo:boolean;
		begin
			num:=0;
			for i:=2 to trunc(sqrt(k)) do
				if sqr(trunc(sqrt(k-i*i)))=k-i*i then begin
					a:=trunc(sqrt(k-i*i));
					b:=i;
					if (a<=b) or (a=0) or (b=0) then continue;
					c:=2*a*b; d:=a*a-b*b;
					a:=c; b:=d;
					if a>b then begin j:=a; a:=b; b:=j; end;
					bo:=false;
					for j:=1 to len do begin
						if a/x[j,1]=b/x[j,2] then begin
							bo:=true; break;
						end;
					end;
					if bo=false then begin
						num:=num+2;
						inc(len);
						x[len,1]:=a; x[len,2]:=b;
					end;
				end;
			exit(num);
		end;
	begin
		readln(r);
		tot:=1; len:=0;
		for i:=1 to trunc(sqrt(r)) do
			if r mod i=0 then begin
				if i<>r div i then
					tot:=tot+find(i)+find(r div i)
				else 
					tot:=tot+find(i);
			end;
		tot:=tot*4;
		writeln(tot);
	end.
Category: 数学题 | Tags:

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