CODE FESTIVAL 2017 qual B C 3 Steps（补题）

总感觉这题是个题意杀，理解错题目了，看了好久才发现题目意思：操作是让，只要两点没有直接相连，而且只要有一条路的距离3，就可以把这两点连接起来。

按照题解中讲的，可以把图分为二分图和非二分图来解。不过题解中的操作我没看懂。。但是画几个图看看就很清除了。

先说二分图：

可以看到，两个点集中，斜对着的点的距离都是3，比如说点对1，2和点对3，4，都是距离为3的点，直接连上就行。

假设两个点集点的数量分别为c1，c2，当把所有这样的点对连接后，总共有c1*c2条边。同一点集中任意亮点距离为2.

再说非二分图。

这个图就是非二分图了，然后画线，连接距离为3的点，可以先按照上边那个二分图那样先把线画满，然后再连接同一个点集中点与点之间的连线。

按照二分图的方式连完线后，会发现这里有一个1-3之间的线，5-2之间的距离本来为2，多了1-3，就多了一条距离为3的路线，且5-2之间没有直接相连，

可以连接一条线，然后再连接别的，这样距离为2的两个点都会因为多那么一条线，从而多了一个距离为3的路线，所以要连接起来，最后连接成一个完全图。

总共n*(n-1)/2条线。

那么也就知道这题的答案了。。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

struct Edge

{

    int to,next;

}edge[MAXN*2];

int head[MAXN];

int tot;

int col[MAXN];

long long c1,c2;

bool flag;

void addedge(int u, int v)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void dfs(int u, int color)

{

    if(flag) return;

    col[u] = color;

    if(color == 1)

        ++c1;

    else

        ++c2;

    for(int i = head[u]; i != -1; i = edge[i].next)

    {

        int v = edge[i].to;

        if(!col[v])

            dfs(v,3-color);

        else if(col[v] == color)

        {

            flag = true;

            return;

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    long long n,m;

    cin >> n >> m;

    int u,v;

    memset(head,-1,sizeof(head));

    memset(col,0,sizeof(col));

    c1 = c2 = tot = 0;

    flag = false;

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

    {

        cin >> u >> v;

        addedge(u,v);

        addedge(v,u);

    }

    dfs(1,1);

    if(flag)

        cout << n*(n-1)/2-m;

    else

        cout << c1*c2-m << endl;

    return 0;

}

巴特西

CODE FESTIVAL 2017 qual B C 3 Steps（补题）

最新文章

热门文章