bzoj 3562【SHOI2014】神奇化合物

Description

科学家最近发现了一种高分子有机化合物 SHTSC。这种物质的分子由单个或多个原子组成,原子之间通过化学键相互连接。SHTSC 十分不稳定,其原子之间的化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。然而,令科学家们大为惊异的是,SHTSC 在变化过程中始终保持着一种特殊的性质:即不存在这样的原子序列 a1,a2,...,an(n>3)满足 a1 与 a2、a2 与a3、......、an-1 与 an 以及 an 与 a1 都通过化学键相连,但它们之间却没有其他化学键相连的情况。现在科学家将 SHTSC 的原子由 1 到 n 标号,并告诉你SHTSC 的初始形态以及原子之间的化学键变化情况,他们想知道在实验过程中的某些时刻 SHTSC 分裂成了多少个分子?

Input

第一行两个整数:n, m。表示 SHTSC 的总原子个数以及初始的化学键数。
从第二行开始的 m 行,每行两个整数 a, b (1≤a,b≤n)。表示编号为 a, b 的两个原子在初始状态中有化学键相连。数据保证每对 a, b 只出现一次。
第 m+2 行有一个整数:q。表示实验的总操作数。
之后 q 行中的每一行为以下三种操作当中的一种:
1、A i j 表示 i 号原子与 j 号原子之间形成了一条新的化学键;
2、D i j 表示 i 号原子与 j 号原子之间原有的化学键断裂了;
3、Q 询问当前 SHTSC 分裂成了多少个不同的分子。
数据保证所有的实验操作都是合法的。
n≤5000,m≤200000,q≤10000。

Output

对于每个 Q 操作,输出一行一个整数,为相应时刻的分子个数。

Sample Input

7 10
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
2 5
10
Q
D 2 5
Q
D 5 6
D 5 7
Q
A 2 5
Q
A 5 6
Q

Sample Output

1
2
3
2
1

题解:
非常妙的一道题
发现操作数量比较小
那么断开的数量就更小了, 有一些边自始至终都没有被断开过
我们先看一看暴力的复杂度
用并查集维护每一个连通块, A的复杂度是并查集合并的复杂度, Q可以做到 $O(1)$ , 对于一个D操作, 我们需要遍历断开的两部分的其中一个部分, 按照最坏情况分析是 $O(nq)$ 的, 但是发现有一些边没有被断开过, 那么缩点, 直接当做一个点来做, 这样大大降低复杂度, 而且D操作如果数量较多,那么缩点后的连通块的数量会很快的增加, 每一个连通块的size就会比较小, 这样总复杂度也比较低
那就是这样了, 所以这题的做法就是暴力?

代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 5001
#define M 530005
struct node2
{
    char q;
    int a,b;
}f[200005],Q[10005];
struct node
{
    int v,next;
}edge[M];
int head[N],set[N];
bool d[N][N],v[N];
int e[N][N];
int id,ans;
void add(int a,int b)
{
    edge[id].v=b;
    edge[id].next=head[a];
    head[a]=id++;
}
void init(int n)
{
    memset(head,-1,sizeof(head));
    id=ans=0;
    for(int i=1;i<=n;i++)set[i]=i;
}
int find(int x)
{
    if(x!=set[x]) return set[x]=find(set[x]);
    return set[x];
}
void merge(int x,int y)
{
    set[find(y)]=find(x);
}
 
bool dfs(int a,int b)
{
    if(a==b) return true;
    for(int i=head[a];~i;i=edge[i].next)
    {
        int to=edge[i].v;
        if(e[a][to]>0&&!v[to])
        {
            v[to]=true;
            if(dfs(to,b)) return true;
        }
    }
    return false;
}
int n;
void addedge(int a,int b)
{
    memset(v,false,sizeof(v));
    if(!dfs(a,b)) ans--;
    e[a][b]++;
    e[b][a]++;
    add(a,b);
    add(b,a);
}
void del(int a,int b)
{
    memset(v,false,sizeof(v));
    e[a][b]--;
    e[b][a]--;
    if(!dfs(a,b)) ans++;
}
inline int ReadInt()
{
    char ch = getchar();
    int data = 0;
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    }while (ch >= '0' && ch <= '9');
        return data;
}

int main()
{
        #ifdef LZT
        freopen("in","r",stdin);
        #endif
    int m,a,b,q;
    n=ReadInt();
    m=ReadInt();
    init(n);
    for(int i=1;i<=m;i++)
    {
        f[i].a=ReadInt();
        f[i].b=ReadInt();
    }
    q=ReadInt();
    for(int i=1;i<=q;i++)
    {
        scanf("%s",&Q[i].q);
        if(Q[i].q!='Q')
        {
            Q[i].a=ReadInt();
            Q[i].b=ReadInt();
            if(Q[i].q=='D') d[Q[i].a][Q[i].b]=d[Q[i].b][Q[i].a]=true;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(!d[f[i].a][f[i].b]) merge(f[i].a,f[i].b);
    }
    for(int i=1;i<=n;i++)
    {
        if((set[i]=find(i))==i) ans++;
    }
    for(int i=1;i<=m;i++)
    {
        if(set[f[i].a]!=set[f[i].b]) addedge(set[f[i].a],set[f[i].b]);
    }
    for(int i=1;i<=q;i++)
    {
        if(Q[i].q=='Q') printf("%d\n",ans);
        else if(Q[i].q=='D') del(set[Q[i].a],set[Q[i].b]);
        else addedge(set[Q[i].a],set[Q[i].b]);
    }
    return 0;
}

最后编辑于：2018.07.15 19:48:55