jiry_2's Blog

赤果果的费用流，一下子就想出来了。类似于最少路径覆盖，但是要用费用流。由于保证可以一遍覆盖，那么就费用流也就保证是一条路径覆盖所有的点。这样的话就是最小路径覆盖的加强版。把每个点拆成两个点。如果I到J有一条边就往I1向J2连一条费用为时间，流量为1的边，由源向每个I1，每个I2向汇连一条费用为0流量为1的边，它的费用流结果就是答案。开始我很SB的把瞬移都当成边连进去，然后就T得一塌糊涂，其实只要从源向每个I2连一条流量为1费用为瞬移时间的边即可，简单粗暴，就AC了。

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