jiry_2's Blog

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

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.