BZOJ1927 Starrace - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ1042 Coins
BZOJ3288 Mato矩阵

BZOJ1927 Starrace

Hoblovski posted @ 2014年7月11日 16:25 in Solutions with tags BZOJ 费用流 啪啪啪 , 1379 阅读
题意
给定无向图G,你需要访问所有结点恰好1次.移动方式有2种
1.跳转,代价为跳转终点的点权
2.行走,代价为行走过的边的边权,且只能从小编号走到大编号.
初始时你只能跳转.最小化总代价.
N!>800,M!>15000
 
Tag 费用流,啪啪啪
 
题目模型是DAG,丧心病狂地在开头加了无向www
最优答案显然是{跳转,行走链,跳转,行走链...}
考虑如果全部使用跳转,代价显然是Sigma(Ai)
如果把v的跳转改为(u,v,w)的行走则代价减少
Av-w
易证答案不会暴int显然中间过程不会暴int不会出现负环(我的省选啊啊被费用流负环坑死100分)
 
=>DAG的最小路径覆盖
如果全部新起路径则代价为Sigma(1)
新起的v改为(u,v)则代价减少1
建二分图拆点,(u,v)=>(X(u),Y(v),1)
所以答案=N-最大权匹配
 
类比,本题建二分图,(u,v,w)=>(X(u),Y(v),Av-w)
这里答案=Sigma(Ai)-最大权匹配,ZKW大法好哦艹逼我重拾KM哦艹只能EKSPFA了
 
证明 该建图能求出题目的解
1.所有解都是合法解
不合法
1.不满足任何点被访问1次
初始化认为都是跳转,之后取消跳转必定加入行走,加入行走必定取消跳转,该点一定合法
2.行走方案非法
任何(X(u),Y(v))表示原图中走到u后走到v,建图时保证u<v故一定是合法的
3.答案和真实答案相异
最开始的时候全部跳转,虽不最优但同于真实答案,之后每次调整保证该性质的保持
2.最优解能够被该算法求出
如上所述,最优解一定是{跳转,行走链,跳转,行走链...}
我们按照最优解的方案一定能构造一个合法匹配,一定能被求出.
故该建图能求出题目的解,证毕.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

以上是在做这道题之前的思维过程,也是漂亮的一个耳光"啪啪啪",如果你按以上方案建图,30分左右.
1.KM会跪
没有完美匹配,KM必跪,除非加冗余边,加了更跪.在
2.ZKW会跪
Orz真正理解zkw了的写dis数组的神牛,而且这题卡zkw
3.建图没有问题不过..
 
我们来看Cha数据
4 4
62 7 23 23 
1 2 6
1 3 6
2 3 9
3 4 1
 
如果按照一般的费用流建图,为了达到最大流量3我们要增大费用!
......
对,我们还需要再加一条边(u,T,1,0)表示单纯的只跳转该点的情况.
......
啪啪啪的一声,耳光.为什么我建图都对了只有30分吖.原因在这里.
顺便标程没看懂
 
{$INLINE ON}
program bzoj1927;
 
type tnode=record
        n,c,w,next:longint;
     end;
 
const maxn=2017;
      maxm=1000017;
      maxint=longint($3f3f3f3f);
      e9=1000000000;
 
var g,q,dis,dlt,arc,pre,a:array[0..maxn] of longint;
    v:array[0..maxn] of boolean;
    mem:array[0..maxm] of tnode;
    barc:array[0..maxn,0..maxn] of boolean;
    n,m,memsize,st,trm,frt,rer,cost,flow,sa:longint;
 
function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;
function max(i,j:longint):longint; inline; begin
if i>j then exit(i) else exit(j);  end;
 
procedure insnbs(u,v,ic,iw:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; c:=ic; w:=iw; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; c:=0; w:=-iw; next:=g[v];
end; g[v]:=memsize;
end;
 
procedure ek_spfa;
var head,tail,u,w,t1:longint;
begin
cost:=0; flow:=0; dis[trm]:=0; while dis[trm]<maxint do begin
        fillchar(dis,sizeof(dis),$3f); frt:=0; rer:=1; q[1]:=st; v[st]:=true; dis[st]:=0; dlt[st]:=maxint; pre[st]:=0;
        while frt<>rer do begin frt:=frt mod maxn+1; head:=q[frt];
                t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                        if (dis[tail]>dis[head]+mem[t1].w)and(mem[t1].c>0) then begin
                                dis[tail]:=dis[head]+mem[t1].w;
                                pre[tail]:=head;
                                arc[tail]:=t1;
                                dlt[tail]:=min(dlt[head],mem[t1].c);
                                if not v[tail] then begin rer:=rer mod maxn+1; q[rer]:=tail; v[tail]:=true; end;
                        end; t1:=mem[t1].next;
                end; v[head]:=false;
        end; if dis[trm]<maxint then begin
                inc(flow,dlt[trm]); inc(cost,dlt[trm]*dis[trm]); u:=trm; w:=dlt[trm];
                while u<>st do begin dec(mem[arc[u]].c,w); inc(mem[arc[u]xor 1].c,w); u:=pre[u]; end;
        end;
end;
end;
 
procedure init;
var i,j,k,u,v,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1; readln(n,m); st:=n<<1+1; trm:=st+1;
for i:=1 to n do begin read(a[i]); inc(sa,a[i]); insnbs(st,i,1,0); insnbs(i+n,trm,1,0); insnbs(i,trm,1,0); end;
for i:=1 to m do begin readln(u,v,w); if u>v then begin k:=u; u:=v; v:=k; end;
        if w<a[v] then insnbs(u,n+v,1,w-a[v]);
end; n:=n<<1+2;
end;
 
begin
init;
ek_spfa;
writeln(sa+cost);
end.

 

Avatar_small
JNVST Result 2022 说:
2021年11月13日 15:56

For Jawahar Navodaya Vidyalayas, the Navodaya Entrance Exam Result 2022 or JNVST Result 2022 will be issued on the Navodaya Vidyalaya Samiti website. The Navodaya class 6 admission official web portal JNVST Result 2022 allows students who took the 6th Class entrance exam to check their details and download their results.

Avatar_small
Alyssa 说:
2023年1月05日 19:59

The BZOJ1027 Starrace is a 2D top-down racing game released on August 8, 2019. The game features 8-bit graphics and chiptune music. The player real estate agent Glen Ellyn controls a spaceship racing through an asteroid field. The goal of the game is to reach the finish line before the other racers.

Avatar_small
HASDWQ 说:
2023年5月02日 19:24

Outstanding Service! Great Execution of their plans in work! They are just perfect! I would like to recommend them to everyone out there! You will not regret it! ready mix concrete supplier

Avatar_small
HASDWQ 说:
2023年5月02日 19:37

Outstanding Service! Great Execution of their plans in work! They are just perfect! I would like to recommend them to everyone out there! You will not regret it! tms doctor

Avatar_small
HASDWQ 说:
2023年5月02日 19:49

If you are an internet user on daily basis then must checkout this site. It has been an amazing experience. Believe me it’s totally worth of your time. Suggested to everyone! tms therapy for depression

Avatar_small
www.model-paper.in 说:
2023年5月20日 15:36

Model-paper strives to provide better service in various formats, and we do not sell or give away your personal information other than public information provided by you. We are extremely concerned about email spam and strive to protect every email as much as possible.In some instances, your mail may be made public.www.model-paper.in Model-paper strives to provide better service in various formats, and we do not sell or give away your personal information other than public information provided by you.We are extremely concerned about email spam and strive to protect every email as much as possible.In some instances, your mail may be made public.

Avatar_small
uburt.in 说:
2023年6月27日 18:14

You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, when creating an account on any KRA's eKYC site. Following verification, uburt.in you must give a copy of your Aadhar card that has been self-attested. You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, when creating an account on any KRA's eKYC site. Following verification, you must give a copy of your Aadhar card that has been self-attested.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter