hdu 6016 Count the Sheep（思维）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6016

题意：给定男羊和女羊的朋友关系，即给定一个图，问从任意一只羊开始连续数四只不相同的羊的方法数。

这题挺简单的就是需要动一下脑子，我们只要找到关系A-B-C-D即可，且关系址建立在男女羊之间。

就是说我们只要找到男羊-女羊-男羊-女羊，或者女羊-男羊-女羊-男羊即可。

于是那只要找到任意一种方式的总数然后乘2即可。

拿后一种关系为例。

ans[i]表示i号女羊有几个男羊朋友vc[i]存储与i号男羊有关系的女羊。

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

int count = vc[i].size() - 1;

for(int j = 0 ; j <= count ; j++) {

sum += ((ans[vc[i][j]] - 1) * count);

}

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <cstdio>

using namespace std;

typedef long long ll;

const int M = 1e5 + 10;

vector<int>vc[M];

int ans[M];

int main() {

    int t;

    scanf("%d" , &t);

    while(t--) {

        int n , m , k;

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

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

            vc[i].clear();

        }

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

            ans[i] = 0;

        }

        while(k--) {

            int a , b;

            scanf("%d%d" , &a , &b);

            ans[b]++;

            vc[a].push_back(b);

        }

        ll sum = 0;

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

            int count = vc[i].size() - 1;

            for(int j = 0 ; j <= count ; j++) {

                sum += (ll)((ans[vc[i][j]] - 1) * count);

            }

        }

        printf("%lld\n" , sum * 2);

    }

    return 0;

}

巴特西

hdu 6016 Count the Sheep（思维）

最新文章

热门文章