Codeforces 553C Love Triangles(图论)

Solution：

　　比较好的图论的题。

要做这一题，首先要分析love关系和hate关系中，love关系具有传递性。更关键的一点，hate关系是不能成奇环的。

看到没有奇环很自然想到二分图的特性。

那么当前的任务是先二分染色，判断给定的边是否有冲突，并且缩点。

假设缩完点后图中只身下k个点。这k个点的hate关系满足二分图的关系。

那么计算组合数，共2^（k-1）种方法。

#include <bits/stdc++.h>

using namespace std;

const int N = ;

typedef pair<int, int> ii;

int  vis[N], n, m , flag , s;

vector<ii> E[N];

void dfs (int x, int k)

{

    vis[x] = k;

    --s;

    for (auto &i : E[x]) {

        if (!~vis[i.first]) {

            dfs (i.first, k ^ i.second);

        } else {

            if ( (vis[x]^vis[i.first]) != i.second) {

                flag = ;

                return ;

            }

        }

        if (flag) return;

    }

}

int main()

{

    memset (vis, -, sizeof vis);

    ios::sync_with_stdio (  );

    cin >> n >> m;

    s = n;

    for ( int i = , u, v, c; i <= m; ++i ) {

        cin >> u >> v >> c;

        E[u].push_back (make_pair (v, c ^ ) );

        E[v].push_back (make_pair (u, c ^ ) );

    }

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

        if (!~vis[i] && !E[i].empty() ) {

            ++s;

            dfs (i, );

        }

        if (flag) {

            cout <<  << endl;

            return ;

        }

    }

    long long  ans = , p = ;

    --s;

    while ( s >  ) {

        if ( s &  ) ans = ans * p % ;

        p = ( p * p ) % ;

        s >>= ;

    }

    cout << ans << endl;

}

巴特西

Codeforces 553C Love Triangles(图论)

最新文章

热门文章