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 费用流 啪啪啪 , 921 阅读
题意
给定无向图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.

 


登录 *


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