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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Spoj287】【Smart Network Administrator】  

2014-03-27 20:23:52|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题目大意:一个村庄地图是个无向图,然后1号人家装了wifi(好像原题是光缆),然后其他地方的人要蹭wifi就得连网线到1号人家,网线沿着边依次连到1号人家,每一条完整的网线有一种颜色,然后网管(跟这家伙有关系么?!)要求各条街道的网线的颜色必须不相同,且要求最多颜色种数的街道的颜色种数最少,求这个最少值。
     可以二分答案c(其实咱一开始想的是枚举,不过可能低效了...),然后把每一条边拆成两条容量为c的边,源点给除了1之外的每一户要蹭wifi的人连一条容量为1的边,然后1连汇点,跑最大流如果最大流为想蹭wifi的人的数目则答案往下二分,否则往上。然后就没了。
=================================================

const maxn=710;
      maxm=500010;
type edge=record
     u,v,w,pre:longint;
     end;

var e:array[0..maxm]of edge;
    last,d,que:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    tot,n,m,t: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,u,tmp:longint;
begin
  fillchar(v,sizeof(v),false);
  fillchar(d,sizeof(d),0);
  l:=0;r:=1;v[s]:=true;
  que[l]:=s;
  while l<r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (e[tmp].w>0)and(not v[e[tmp].v])then
         begin
           d[e[tmp].v]:=d[u]+1;
           v[e[tmp].v]:=true;
           que[r]:=e[tmp].v;
           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 (a=0)or(p=t)then exit(a);
  flow:=0;
  tmp:=last[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(e[tmp].w,f);
           dec(a,f);
           inc(flow,f);
           inc(e[tmp xor 1].w,f);
           if a=0 then break;
         end;
      end;
     tmp:=e[tmp].pre;
   end;
  exit(flow);
end;

function dinic(s,t:longint):longint;
var ans:longint;
begin
  ans:=0;
  while bfs(s,t) do
   ans:=ans+dfs(s,maxlongint,t);
  exit(ans);
end;

procedure init;
var i,j,k,l,r,mid,sav:longint;
begin
  read(n,m,k);
  fillchar(last,sizeof(last),255);
  tot:=-1;sav:=k;
  for i:=1 to k do
   begin
     read(j);
     addedge(0,j,0);
   end;
  l:=1;r:=k;
  for i:=1 to m do
   begin
     read(j,k);
     addedge(j,k,0);
     addedge(k,j,0);
   end;
  addedge(1,n+1,0);
  while l<r do
   begin
     mid:=(l+r)shr 1;
     for i:=0 to tot do
      begin
       if (e[i].u=0)or(e[i].v=0)then
          if i and 1=0 then e[i].w:=1
                       else e[i].w:=0
       else
       if (e[i].u=n+1)or(e[i].v=n+1)then
          if i and 1=0 then e[i].w:=sav
                       else e[i].w:=0
       else
          if i and 1=0 then e[i].w:=mid
                       else e[i].w:=0;
      end;
     if dinic(0,n+1)=sav then r:=mid
                         else l:=mid+1;
   end;
  writeln(l);
end;

begin
  read(t);
  for t:=1 to t do
    init;
end.

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

历史上的今天

评论

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

页脚

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