注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【CH Round#30】【D-男女搭配】  

2014-04-10 15:49:53|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    CH评测姬挂了。贴下代码。
    0.0另外没加slack优化的一份代码貌似都能过,太可怕了...orz
=================

program ch30d;
var g:array[0..1010,0..1010]of longint;
    x,y,slack,h,likem,likew,s,t:array[0..1010]of longint;
    ans,n,time:longint;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

function dfs(p:longint):boolean;
var i:longint;
begin
  s[p]:=time;
  for i:=1 to n do
   if (t[i]<>time)then
    if (x[p]+y[i]=g[p][i]) then
    begin
      t[i]:=time;
      if (h[i]=0)or(dfs(h[i])) then
       begin
         h[i]:=p;
         exit(true);
       end;
    end
   else slack[p]:=min(slack[p],x[p]+y[i]-g[p][i]);
  exit(false);
end;

procedure modify;
var tmp,i:longint;
begin
  tmp:=maxlongint;
  for i:=1 to n do
   if s[i]=time then
    tmp:=min(tmp,slack[i]);
  for i:=1 to n do
   if s[i]=time then
     dec(x[i],tmp);
  for i:=1 to n do
   if t[i]=time then
     inc(y[i],tmp);
end;

procedure init;
var i,j:longint;
begin
  read(n);
  for i:=1 to n do read(likem[i]);
  for i:=1 to n do read(likew[i]);
  for i:=1 to n do read(x[i]);
  for i:=1 to n do read(y[i]);
  for i:=1 to n do
   for j:=1 to n do
     g[i][j]:=-(ord(likem[i]<>j)*x[i]+ord(likew[j]<>i)*y[j]);
  fillchar(x,sizeof(x),0);
  fillchar(y,sizeof(y),0);
  fillchar(s,sizeof(s),0);
  fillchar(t,sizeof(t),0);
  time:=0;
  for i:=1 to n do
   begin
    x[i]:=g[i][1];
    for j:=2 to n do
     if x[i]<g[i][j] then x[i]:=g[i][j];
   end;
  for i:=1 to n do
   begin
     repeat
       inc(time);
       for j:=1 to n do slack[j]:=maxlongint;
       if dfs(i) then break
                 else modify;
     until false;
   end;
  ans:=0;
  for i:=1 to n do
   ans:=ans+g[h[i]][i];
  write(-ans);
end;

begin
  assign(input,'input');reset(input);
  init;
  close(input);
end.

  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017