codeforces553C Love Triangles

题目链接：codeforces553C Love Triangles

我们来看一下对于一个合法三角形可能出现的边

我们发现，在确定了两边之后，第三条边是什么也就随之确定了

我们用\(1\)表示\(love\)，用\(0\)表示\(hate\)

那么\(111-->11,1\)

\(100-->\ 00,1/10,1\)

我们发现，当两条边的数字相同时，第三条边的数字为\(1\)，否则为\(0\)

很明显这个条件在反过来时也是成立的

这有什么作用？

我们推广一下：假设我们已知一个点\(u\)它连出去的所有边，那么我们能得到什么？

我们能得到的是这个图的情况，比如两条边\((u,v),(u,w)\)，由它们是否相同可以推出\((v,u)\)的情况

所以我们考虑去推出与一个点相连的所有边的情况，我们取这个点为1

那么在一个联通块内的所有点与1点的边的关系是有一个相对关系的，即在确定了一条边的颜色后，我们可以确定整个联通块的边的颜色

所以对这个联通块我们有2种染色方式

再在减去1号点所在的联通块的颜色应该是已知的，所以最后的答案就是2的联通块数-1的乘方

在找联通块的dfs中顺便判掉是否有解

#include<iostream>

#include<string>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

using namespace std;

const int maxd=1e9+7;

struct node{

    int to,nxt,cost;

}sq[200200];

int n,m,all=0,head[100100],tag[100100];

bool no_so=0;

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

void add(int u,int v,int w)

{

    all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;

}

void dfs(int u)

{

    int i;

    for (i=head[u];i;i=sq[i].nxt)

    {

        int v=sq[i].to,w=sq[i].cost;

        if (tag[v]==-1)

        {

            if (w==1) tag[v]=tag[u];else tag[v]=1-tag[u];

            dfs(v);

        }

        else

        {

            if ((w==1) && (tag[v]!=tag[u])) {no_so=1;return;}

            else if ((w==0) && (tag[v]==tag[u])) {no_so=1;return;}

        }

    }

}

int main()

{

    n=read();m=read();int i;

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

    {

        int u=read(),v=read(),w=read();

        add(u,v,w);add(v,u,w);

    }

    memset(tag,-1,sizeof(tag));int cnt=-1;

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

    {

        if (tag[i]==-1)

        {

            tag[i]=0;

            dfs(i);

            if (no_so) {printf("0");return 0;}

            else cnt++;

        }

    }

    long long ans=1;

    for (i=1;i<=cnt;i++) ans=(ans*2)%maxd;

    printf("%I64d",ans);

    return 0;

}

巴特西

codeforces553C Love Triangles

最新文章

热门文章