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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

边表运用(星际大战)  

2014-03-04 20:40:31|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
边表是一个很有用的结构,许多难题本来TLE,若改成用边表存都能水过去。首先用TOT表示当前的边数总量,而后开个记录类型,里面定义变量BEFORE,S,END分别表示,上一条公用头结点S的边,再开一个数组Index[I],以I为头结点的边的序号。
一开始读入X,Y表示X和Y之间有一条边,那么这么做:add(X,Y);
int add(int a,int b)
 {
 tot++;
 addedge[tot].s=a;
 addedge[tot].end=b;
 addedge[tot].next=Index[a];第一个以a为顶点的Index[A]=0,所以下次搜边的时候用while(NOW>0);
 Index[a]=tot;
 }
对于星际大战,倒着做并查集,那么删边变成添边,而数据范围很大,所以用边表实现,具体代码:
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
 int next;int s;int end; 
}addedge[400100];
int tot,i,j,m,k,n,x,y;
int harm[400100],fa[400100],Index[400100],ans[400100];
bool able[400100];

int add(int a,int b)
 {
 tot++;
 addedge[tot].s=a;
 addedge[tot].end=b;
 addedge[tot].next=Index[a];
 Index[a]=tot;
 }
int find(int w)
 {
 if (fa[w]==w) return w;
 fa[w]=find(fa[w]);
 return fa[w];
 }
 
int main()
{
 scanf("%d%d",&n,&m);tot=0;
 for (i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    add(x+1,y+1);add(y+1,x+1);
    } 
    
memset(able,true,sizeof(able));
for (i=1;i<=n;i++) fa[i]=i;


scanf("%d",&k);for (i=1;i<=k;i++)
                 {
                 scanf("%d",&harm[k-i+1]);
                 harm[k-i+1]++;able[harm[k-i+1]]=false;
                 }
                 
                 
 for (i=1;i<=tot;i++)
     if ((able[addedge[i].s])&&(able[addedge[i].end]))
            {
            int q=find(addedge[i].s);int p=find(addedge[i].end);
            if (q!=p) fa[q]=p;
            }
for (i=1;i<=n;i++)            
            if ((find(i)==i)&&(able[i])) ans[k+1]++;
int cnt=ans[k+1];
for (i=1;i<=k;i++){
              able[harm[i]]=true;
              int now=Index[harm[i]];
                while (now>0)
                        {
                        if (able[addedge[now].end]){
                int q=find(harm[i]);
                int p=find(addedge[now].end);
if (q!=p)
      {fa[q]=p;cnt--;}     
                                                }
                         now=addedge[now].next;        
                        }
                cnt++;        
                ans[k-i+1]=cnt;
                   }
for (i=1;i<=k+1;i++) 
printf("%d\n",ans[i]);
return 0;
}
  评论这张
 
阅读(868)| 评论(1)

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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