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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3562][SHOI2014]神奇化合物  

2015-03-27 20:17:57|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3562: [SHOI2014]神奇化合物

比较厉害的暴力,利用忽略无用信息的思路

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 5000+10;
const int M = 200000+100;
 
int scan(){
    char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
    if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
    while('0'<=cc&&cc<='9'){re=re*10+cc-'0';  cc=getchar();}return re*fh;
}
typedef pair<int,int>Edge;
Edge edges[M];
short de[M];
int n,m,ask[N*2][3],block[N],T,fa[N],vis[N];
short v[N][N];
int find(int x){if(!fa[x])return x;return fa[x]=find(fa[x]);}
struct Point{
    Point(){next=NULL;}
    Point *next;int from,d;
    void push(int a,int b){
        Point *l = new Point;
        l->from=a;l->d=b;
        l->next=next;next=l;
    }
}point[N];
void AddEdge(int from,int to){
    int a,b;a=block[from];b=block[to];
    point[a].push(from,to);
    point[b].push(to,from);
    v[from][to]=v[to][from]=1;
}
void dfs(int x){
    vis[x]=T;
    for(Point *i = point[x].next;i!=NULL;i=i->next)
    if(vis[block[i->d]]!=T && v[i->from][i->d]){
        dfs(block[i->d]);
    }
}
int main(){
    int i,j,a,b;
    n = scan();m = scan();
    for(i=1;i<=m;i++){
        a=scan();b=scan();
        if(a>b)swap(a,b);
        edges[i]=Edge(a,b);
    }
    sort(edges+1,edges+1+m);
    int q=scan();
    for(i=1;i<=q;i++){
        char cc;
        scanf(" %c",&cc);
        switch(cc){
            case'Q':
                ask[i][0]=0;
            break;
            case'A':
                ask[i][0]=1;
                ask[i][1]=scan();ask[i][2]=scan();
            break;
            case'D':
                ask[i][0]=2;
                a=ask[i][1]=scan();b=ask[i][2]=scan();
                if(a>b)swap(a,b);
                Edge now = Edge(a,b);
                j = lower_bound(edges+1,edges+1+m,now)-edges;
                if(edges[j]==now)de[j]=1;
            break;
        }
    }
    //for(i=1;i<=m;i++)printf("%d ",de[i]);printf("\n");
    for(i=1;i<=m;i++)
    if(!de[i]){
        a=edges[i].first;b=edges[i].second;
        a=find(a);b=find(b);
        if(a!=b){
            if(i&1)fa[a]=b;
            else fa[b]=a;
        }
    }//else printf("%d %d\n",edges[i].first,edges[i].second);
    for(i=1;i<=n;i++){
        a = find(i);
        if(!block[a])block[a]=++block[0];
        block[i]=block[a];
    }
    //for(i=1;i<=n;i++)printf("%d ",block[i]);printf("\n");
    for(i=1;i<=m;i++)
    if(de[i])
    AddEdge(edges[i].first,edges[i].second);
    for(i=1;i<=q;i++)
    switch(ask[i][0]){
        case 0:
            T++;vis[0]=0;
            for(j=1;j<=block[0];j++)
            if(vis[j]!=T){
                vis[0]++;
                dfs(j);
            }
            printf("%d\n",vis[0]);
        break;
        case 1://ADD
            a=ask[i][1];b=ask[i][2];
            a=find(a);b=find(b);
            if(a!=b)AddEdge(ask[i][1],ask[i][2]);
        break;
        case 2://DEL
            v[ask[i][1]][ask[i][2]]=v[ask[i][2]][ask[i][1]]=0;
        break;
    }
    return 0;
}

题解:
边多但是删除操作少,所以把用不着的边固定住,点缩到一起然后暴力
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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