Kattis - doubleclique (图论)

From : North American Invitational Programming Contest 2018

给你一个图，以及它的补图。如果部分点在原图中是团，并且其他的所有点在补图中也是团，那么就叫做一个双团。

要求计算图中双团的数量。

这篇博客使我理解了这个问题：zro https://www.cnblogs.com/clrs97/p/8730429.html orz

如果其他点在补图中构成团，那么这些点在原图中是一个独立集。

可以想到，满足条件的状态是 (团的点数) × (团的点数 - 1) + 独立集点的度数和 = 团点的度数和。

因为 (团的点数) × (团的点数 - 1) = 团中所有边构成的度数，所以剩下的度数就是团的点与独立集的点之间的边所构成的度数了。

这样我们可以找出一种可行方案。

那么剩下的方案，可能是

1：团中一个点加入到独立集中:

2：也可能是独立集中一个点加入到团中

3：1+2

分别统计答案即可。

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = *1e5 + ;

const LL M = 1e9+;

int d[maxn], sum[maxn];

int main()

{

        int n, m;

        scanf("%d%d", &n, &m);

        for (int i = ; i <= m; i++)

        {

                int x, y;

                scanf("%d%d", &x, &y);

                d[x]++, d[y]++;

        }

        sort(d+, d++n);

        reverse(d+, d++n);

        for (int i = ; i <= n; i++)

                sum[i] = sum[i-] + d[i];

        LL ans = ;

        int mid = ;

        for (int i = ; i <= n; i++)

                if (1ll*i*(i-)+sum[n]-sum[i] == sum[i])

                {

                        ans++;

                        mid = i;

                        break;

                }

        //找到一种可行方案。

        //团中的点的度数一定大于等于独立集中的点的度数，所以排个序直接枚举断点即可。

        if (!ans)

        {

                printf("0\n");

                return ;

        }

        for (int i = ; i <= mid; i++)

                if (1ll*(mid-)*(mid-)+sum[n]-sum[mid]+d[i] == sum[mid]-d[i]) ans++;

        for (int i = mid+; i <= n; i++)

                if (1ll*(mid+)*mid+sum[n]-sum[mid]-d[i] == sum[mid]+d[i]) ans++;

        LL x = , y = ;

        for (int i = ; i <=mid; i++)

                if (d[i] == d[mid]) x++;

        for (int i = mid+; i <= n; i++)

                if (d[i] == d[mid]) y++;

        ans = (ans+x*y)%M;

        printf("%lld", ans);

}

巴特西

Kattis - doubleclique (图论)

最新文章

热门文章