계차 제약 최 적 화 된 poj 1201
제목: [1, 50000] 에서 일련의 정점 을 선택 하 는 것 은 일련의 부등식 을 만족 시 키 는 것 이다. [a, b] 에서 적어도 c 개의 정점 이 있 고 선택 하 는 전체 포인트 가 가장 적다.
먼저 가장 좋 은 문 제 를 말 하 다.
1. 최소 분해:
초기 값 을 최소 화하 고 이완 조건 을 이용 합 니 다: d [u] + w [u, v] > = d [v] 수정 (조건 을 만족 시 키 는 값 을 최소 화 합 니 다). 따라서 연결 조건 은 d [v] - d [u] > = w [u, v] 입 니 다.
2. 최대 분해:
초기 값 을 최대 로 부여 하고 이완 조건 을 이용 합 니 다: d [u] + w [u, v] < = d [v] 수정 (조건 을 만족 시 키 는 값 이 가장 큽 니 다). 따라서 연결 조건 은 d [v] - d [u] < = w [u, v] 입 니 다.
이 문제 에 대해 몇 가지 부등식 을 분석 해 야 한다.
1. S [b] - S [a - 1] > = c (제목 조건)
2, 1 > = S [I] - S [I - 1] > = 0 (보증 은 정각 이 고 점차 증가)
2 에서 a, S [I - 1] - S [I] > = - 1 을 출시 합 니 다.
b、S[I]-S[I-1]>=0
그림 을 만 들 면 spfa 가 지나 갈 수 있 습 니 다.처음에는 슈퍼 소스 를 만 들 필요 가 없고 모든 점 을 입단 시 키 기만 하면 된다.
const maxn=50000;maxm=1100000;
var d,tail:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
st,next,sora,cost:array[0..maxm]of longint;
n,ss:longint;
procedure link(x,y,z:longint);
begin
inc(ss);next[tail[x]]:=ss;tail[x]:=ss;sora[ss]:=y;cost[ss]:=z
end;
procedure spfa;
var i,ne,na,h,r:longint;
begin
fillchar(st,sizeof(st),0);
h:=0;r:=1;st[1]:=maxn;
for i:=0 to maxn-1 do begin
inc(r);st[r]:=i;
link(i+1,i,-1);link(i,i+1,0)
end;
fillchar(d,sizeof(d),0);fillchar(v,sizeof(v),false);
repeat
inc(h);ne:=st[h];
i:=ne;
while next[i]<>0 do begin
i:=next[i];na:=sora[i];
if d[ne]+cost[i]>d[na] then begin
d[na]:=d[ne]+cost[i];
if v[na] then begin
v[na]:=false;
inc(r);st[r]:=na
end
end
end;
v[ne]:=true
until h>=r
end;
procedure origin;
var i:longint;
begin
fillchar(tail,sizeof(tail),0);
for i:=0 to maxn do tail[i]:=i;ss:=maxn
end;
procedure init;
var i,x,y,z:longint;
begin
readln(n);
origin;
for i:=1 to n do begin
readln(x,y,z);
link(x-1,y,z)
end;
spfa;
writeln（d[maxn]）
end;
begin
assign(input,'1201.in');reset(input);
init;
close(input)
end.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
