【HDU4677】Graph

这个题调的我真绝望(这个题解的公式也写的我很绝望),写了三遍调了一天才过qwq,蓝瘦香菇
这个题利用了根号分治的思想,我们把按照入度把边分类,所有出入度之和大于\(\sqrt[2]{m}\)的点作为重点,剩下的点作为轻点
那么设重点个数为\(x\),所以\(\frac{x*\sqrt{m}}{2} \lt m\) ,所以\(x \lt 2 * \sqrt{m}\)
那么我们将单次修改和查询的时间复杂度都变为了\(n\sqrt{n}\),就可以接受了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
#define F(i,a,b) for(ri i=a;i<=b;i++)  

using namespace std;

typedef long long lo;

const int s = 100010;

char lin, qwq[20];

lo n, m, du[s], tp[s], col[s], ans[5], su[s][2], head[s][2], q, lx, ly, ci, tot, cnt, sz;

struct in
{
    lo to, ne, co;
}ter[s << 2];

struct es
{
    lo f, l, c;
    inline bool operator < (const es &a) const
    {
        if(f == a.f)
            return l < a.l;
        return f < a.f;
    }
}ing[s];

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(lo &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

inline void rechar(char &x)
{
    x = getchar();
    while(x < 'A' || x > 'Z')
        x = getchar();
}

inline void build(lo fl, lo f, lo l, lo c)
{
    ter[++ tot] = (in){l, head[f][fl], c}, head[f][fl] = tot;
}

int main()
{
    while(~ scanf("%lld%lld", &n, &m))
    {
        tot = cnt = 0;
        for(ri i = 1; i <= n; i ++)
            re(col[i]);
        for(ri i = 0; i < m; i ++)
        {
            re(ing[i].f), re(ing[i].l), re(ing[i].c);
            if(ing[i].f > ing[i].l)
                swap(ing[i].f, ing[i].l);
        }
        sort(ing, ing + m);
        for(ri i = 0, j; i < m; i = j)//合并重边 
        {
            for(j = i + 1; ing[j].f == ing[i].f && ing[j].l == ing[i].l && j < m; j ++)
                ing[i].c += ing[j].c;
            ing[cnt ++] = ing[i];
        }
        sz = sqrt(cnt << 1);//按照根号分治 
        memset(du, 0, sizeof(du)), memset(head, -1, sizeof(head));
        for(ri i = 0; i < cnt; i ++)
            du[ing[i].f] ++, du[ing[i].l] ++;
        for(ri i = 1; i <= n; i ++)//判断所有出入大于m^(1/2)的点,因为设点的个数为X,那么x * m ^ (1 / 2) / 2 < m,所以x < 2 * sqrt(m),这样时间复杂度就降下来了 
            tp[i] = (du[i] >= sz);
        for(ri i = 0; i < cnt; i ++)//重新建没有重边的图 
        {
            lo x = ing[i].f, y = ing[i].l, c = ing[i].c;
            if(tp[x])//重点(度数大于sqrt(m))是被连的,轻点是连出去的 
                build(1, y, x, c);
            else
                build(0, x, y, c);
            if(tp[y])
                build(1, x, y, c);
            else
                build(0, y, x, c);
        }
        memset(ans, 0, sizeof(ans)), memset(su, 0, sizeof(su));
        for(ri i = 0; i < cnt; i ++)
        {
            lo f = ing[i].f, l = ing[i].l, c = ing[i].c;
            if(tp[f])//维护每个点与它相连的两种点所形成的边的边权 
                su[f][col[l]] += c;
            if(tp[l])
                su[l][col[f]] += c;
            ans[col[f] + col[l]] += c;
        }
        printf("Case %d:\n", ++ ci);
        re(q);
        while(q --)
        {
            scanf("%s", qwq), re(lx);
            if(qwq[0] == 'A')
                re(ly), printf("%lld\n", ans[lx + ly]);
            else
            {
                col[lx] ^= 1;
                if(tp[lx])//如果这个点是重点,直接修改
                    for(ri i = 0; i <= 1; i ++)
                        ans[(col[lx] ^ 1) + i] -= su[lx][i], ans[col[lx] + i] += su[lx][i];
                else//否则对与自己相连的轻点修改(不超过sqrt(m)) 
                    for(ri i = head[lx][0]; i > 0; i = ter[i].ne)
                    {
                        int to = ter[i].to;
                        ans[(col[lx] ^ 1) + col[to]] -= ter[i].co;
                        ans[col[lx] + col[to]] += ter[i].co;
                    }
                for(ri i = head[lx][1]; i > 0; i = ter[i].ne)//每次都要修改与自己相连的终边 
                {
                    int to = ter[i].to;
                    su[to][col[lx] ^ 1] -= ter[i].co, su[to][col[lx]] += ter[i].co;//减去原来的方案,加上现在的方案 
                }
            }
        } 
    }
}

2 thoughts

发表评论

电子邮件地址不会被公开。 必填项已用*标注