HDU_6016_(Bestcoder round #92 1002)

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

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

思路：一开始用了dfs没过，报的超时，以为真的会超时，最后发现，犯了个以前常犯的老问题，存边的vector开小了，，这道题需要开

(n+m)的vector。

后来又按官方题解做了一遍，官方题解，也就需要脑袋转一下。要找序列：男--女--男--女，或者女--男--女--男；那么只需要找其中一种，即只找女(1)--男(2)--女(3)--男(4) 的种数，答案为ans*2。枚举(2)号男羊和与(2)号男羊之间有边的一只(3)号女羊，即可确定

一类序列的种数，ans+=(sheep[i]-1)*(sheep[j]-1) i与j之间有边。

dfs：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

#define N 100005

vector<int> sheep[*N];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m,k;

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

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

            sheep[i].clear();

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

        {

            int a,b;

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

            sheep[a].push_back(b+n);

            sheep[b+n].push_back(a);

        }

        long long ans=;

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

        {

            int way=sheep[i].size()-;

            for(int j=;j<sheep[i].size();j++)

            {

                ans+=(sheep[sheep[i][j]].size()-)*way;

            }

        }

        printf("%I64d\n",ans*);

    }

    return ;

}

官方做法：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

#define N 100005

vector<int> sheep[*N];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m,k;

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

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

            sheep[i].clear();

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

        {

            int a,b;

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

            sheep[a].push_back(b+n);

            sheep[b+n].push_back(a);

        }

        long long ans=;

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

        {

            int way=sheep[i].size()-;

            for(int j=;j<sheep[i].size();j++)

            {

                ans+=(sheep[sheep[i][j]].size()-)*way;

            }

        }

        printf("%I64d\n",ans*);

    }

    return ;

}

巴特西

HDU_6016_(Bestcoder round #92 1002)_(dfs)(暴力)

最新文章

热门文章