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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【CF Round#234 div 2】【Dima and Bacteria】  

2014-03-06 01:39:00|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     显然假设某个细菌群互相连通,那么显然从哪个点开始遍历都可以,所以我们记录下每个细菌群是否有细菌被遍历到以及每个细菌是否被遍历,然后每一次找一个没被遍历的细菌群,从中随便找一个点DFS扩展。然后每遍历到一个点就将它的细菌群的细菌数目--,最后DFS完了检查遍,如果有数目=0的那么就是YES,否则就是NO,对于YES再缩点+FLOYD跑SSSP即可。英语题各种吃力,看题大概就占了30分钟,然后傻×的第三题的第二种操作想当然的想错了,以为直接把x,y交换即可,然后调了30分钟才发现错误,最后刚码完D,时间就到了....第一次CF就结束了..
    然后第三天修改完代码来测的时候各种 Judgement failed 。0 0这是不是传说中的评测机咽气了..... 以下待测,只保证4个样例可过....
    然后测了一下,WA第七个点。发现CF可以看数据,百思不得其解的是第七个点应该输出NO的呀...然后又找个谷歌翻译了一段比较关键的判断YES NO的,发现是要间接的走回到该细菌群的任何一个才行(假设只有一个的话,得先走到外面再走回来),但是这样子的话第7组数据就应该错了(这组数据并没有边,可它输出YES),假设这一组对的话,那么第三组数据又错了(第三组也没有边,只不过范围小了点,可它输出No)这题意果断晕了.......
    英文题各种囧。待修改
=====================

program d;
type
  edge=record
  v,w,pre:longint;
  end;

var g:array[0..510,0..510]of longint;
    s,num:array[0..510]of longint;
    v:array[0..510]of boolean;
    vv:array[0..100010]of boolean;
    last:array[0..100010]of longint;
    e:array[0..200010]of edge;
    n,m,k,tot:longint;

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

function find(x:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=k;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if s[mid]=x then exit(mid);
     if s[mid]<x then l:=mid+1
                 else r:=mid;
   end;
  exit(l);
end;

procedure dfs(x:longint);
var tmp:longint;
begin
  tmp:=last[x];
  while tmp<>0 do
   begin
     if (not vv[e[tmp].v])and(e[tmp].w=0)then
      begin
        vv[e[tmp].v]:=true;
        v[find(e[tmp].v)]:=true;
        dec(num[find(e[tmp].v)]);
        dfs(e[tmp].v);
      end;
     tmp:=e[tmp].pre;
   end;
end;


procedure init;
var i,j,l,uu,vvv,ww,x,y:longint;
    flag:boolean;
begin
  read(n,m,k);
  for i:=1 to k do
   begin
     read(s[i]);
     num[i]:=s[i];
     s[i]:=s[i]+s[i-1];
   end;
  fillchar(g,sizeof(g),255);
  fillchar(last,sizeof(last),0);
  tot:=0;
  for i:=1 to k do g[i][i]:=0;
  for i:=1 to m do
   begin
     read(uu,vvv,ww);
     addedge(uu,vvv,ww);
     x:=find(uu);
     y:=find(vvv);
     if x<>y then
      if (g[x][y]>ww)or(g[x][y]=-1) then
       begin
        g[x][y]:=ww;
        g[y][x]:=ww;
       end;
   end;
  fillchar(v,sizeof(v),false);
  fillchar(vv,sizeof(vv),false);
  for i:=1 to k do
   if not v[i] then
    begin
      dfs(s[i-1]+1);
    end;
  flag:=true;
  for i:=1 to k do
   if num[i]=0 then begin writeln('Yes');flag:=false;break;end;
  if flag then begin write('No');exit;end;
  for l:=1 to k do
   for i:=1 to k do
     for j:=1 to k do
     if (i<>j)and(j<>k)and(i<>k)then
     if (g[i][l]>=0)and(g[l][k]>=0)then
      if (g[i][j]>g[i][l]+g[l][k])or(g[i][j]=-1) then
       g[i][j]:=g[i][l]+g[l][k];
  for i:=1 to k do
   for j:=1 to k do
    begin
      write(g[i][j],' ');
      if j=k then writeln;
    end;
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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