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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1934】【Shoi2007】【善意的投票vote】  

2014-04-25 09:25:54|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      题目大意:N个小朋友针对某个答案为yes或no的问题进行了投票,他们每一个人一开始有一个自己的答案,但是他们有朋友,如果一对朋友间的意见不同的话会产生1的不和谐值,然后如果一个小朋友为了朋友爱情之类的理由违背了自己的答案,也会产生1的不和谐值,求每个小朋友应该选择的答案,使得不和谐值最小。

      = =被231908君嘲讽了不会最小割...
      不过本来就不会额><
      咱们把yes和no看成0,1集,那么这道题实际上就是把所有的小朋友看成点,然后实际上就是把点划分成两部分,一部分为0,一部分为1,然后咱们考虑给好朋友之间连容量为1的边,那么这个割实际上就包含了所有的不合的,但是这貌似还不够额...咱们设最后和s连通的都是0,和t连通的都是1,然后假设某个点原来应该是0的话则使它与s连一条容量为1的边,然后某个点原来应该是1的话则使它与t连一条容量为1的边,0.0然后求这个的图的最大流即可?为什么呢?因为每一个割都对应着一个方案吧,即割左边的都是0,右边的都是1,然后代价的确是那么多。
      最近再看一看hbt和pty的最小割模型。
=========================

program bzoj1934;
const maxm=400010;
      maxn=610;

type edge=record
     u,v,w,pre:longint;
     end;
var e:array[0..maxm]of edge;
    last,d,que,cur:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    tot,n,m:longint;

procedure addedge(u,v,w:longint);
begin
  inc(tot);e[tot].u:=u;e[tot].v:=v;e[tot].w:=w;
  e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].u:=v;e[tot].v:=u;e[tot].w:=0;
  e[tot].pre:=last[v];last[v]:=tot;
end;

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

function bfs(s,t:longint):boolean;
var l,r,tmp,u:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(d,sizeof(d),0);
  fillchar(v,sizeof(v),false);
  v[s]:=true;d[s]:=0;
  l:=0;r:=1;
  que[l]:=s;
  while l<r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (not v[e[tmp].v])and(e[tmp].w>0) then
         begin
           que[r]:=e[tmp].v;
           v[e[tmp].v]:=true;
           d[e[tmp].v]:=d[u]+1;
           inc(r);
         end;
        tmp:=e[tmp].pre;
      end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var tmp,f,flow:longint;
begin
  if (p=t)or(a=0)then exit(a);
  flow:=0;
  tmp:=cur[p];
  while tmp<>-1 do
   begin
     if (e[tmp].w>0)and(d[e[tmp].v]=d[p]+1)then
      begin
        f:=dfs(e[tmp].v,min(e[tmp].w,a),t);
        if f<>0 then
         begin
           dec(a,f);
           dec(e[tmp].w,f);
           inc(e[tmp xor 1].w,f);
           inc(flow,f);
           if a=0 then break;
         end;
      end;
     tmp:=e[tmp].pre;
     if tmp<>-1 then cur[p]:=e[tmp].pre;
   end;
  exit(flow);
end;

function dinic(s,t:longint):longint;
var ans,i:longint;
begin
  ans:=0;
  while bfs(s,t) do
   begin
    for i:=0 to n+1 do cur[i]:=last[i];
    ans:=ans+dfs(s,maxlongint,t);
   end;
  exit(ans);
end;

procedure init;
var i,j,u,v:longint;
begin
  read(n,m);
  fillchar(last,sizeof(last),255);
  tot:=-1;
  for i:=1 to n do
   begin
     read(j);
     if j=0 then addedge(0,i,1)
            else addedge(i,n+1,1);
   end;
  for i:=1 to m do
   begin
     read(u,v);
     addedge(u,v,1);
     addedge(v,u,1);
   end;
  write(dinic(0,n+1));
end;

begin
  init;
end.

  评论这张
 
阅读(33)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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