hdu Keep In Touch

时间：2016-08-06 21:56:17 阅读：346 评论：0 收藏：0 [点我收藏+]

Keep In Touch

Accepts: 109

Submissions: 243

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

There are $n$ cities numbered with successive integers from $1$ to $n$ in Byteland. Also, there are $m$ one-way roads connecting the cities. The starting point of the $i$ -th road is $u_i$ while the ending point is $v_i$ .

There are $3$ spies : 007, 008 and 009. They are going to start $q$ secret missions.

During each mission, they may be in three different cities, and they contact each other using interphones. The radio frequency of the $i$ -th city is $w_i$ . Two spies can contact with each other if and only if the absolute value of the difference of radio frequency between the cities where they are in is no more than $K$ . At each moment, three spies must choose a road and go to another city. The time for traveling each road is only a unit of time.

They can choose to end the mission in any city, even in the city where they started the mission. But they are not allowed to end mission in the middle of the roads. Now they want to know, for each mission whose start points are given, what‘s the number of possible ways, during which they can contact with each other at any moment when they are not on roads?

Two ways are considered different if and only if there exists at least one spy at different cities on the same moment.

Note : $3$ spies must end the mission at the same time.

The first line of the input contains an integer $T$ $(1≤T≤10)(1\leq T\leq 10)$ , denoting the number of test cases.

In each test case, the first line of the input contains four integers $n$ $(1≤n≤50),m(0≤m≤n(n?1)2),K(0≤K≤109),q(1≤q≤125000)(1\leq n\leq 50),m(0\leq m\leq \frac{n(n-1)}{2}),K(0\leq K\leq 10^9),q(1\leq q\leq 125000)$ , denoting the number of cities, the number of roads, the upper limit of interphone and the number of missions.

The second line of the input contains $n$ integers $w_1, w_2, ..., w_n$ $(1≤wi≤109)(1\leq w_i\leq 10^9)$ , denoting the radio frequency of the $i$ -th city.

Each of the next $m$ lines contains two integers $u_i,v_i$ $(1≤ui<vi≤n)(1\leq u_i < v_i\leq n)$ , denoting an one-way road. There are no multiple edges in the graph.

Each of the next $q$ lines contains three integers $x,y,z(1≤x,y,z≤n)x,y,z(1\leq x,y,z\leq n)$ , denoting the starting point of the three spies in each mission. You can assume that there are at least one possible way in each mission.

一个无向图，有三个人，起点任意，但是三个人所在城市的频率差值不大于k 每次三人都必须移动到下一个点或者三人选择此时结束任务

问对于起始点i j k 有几种结束方案

记忆化搜索暴力枚举起点状态

/************************************************
┆  ┏┓　　　┏┓ ┆
┆┏┛┻━━━┛┻┓ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　━　　　┃ ┆
┆┃　┳┛　┗┳　┃ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　┻　　　┃ ┆
┆┗━┓　  　┏━┛ ┆
┆　　┃　  　┃　　┆　　　　　　
┆　　┃　  　┗━━━┓ ┆
┆　　┃　 AC代马 　　┣┓┆
┆　　┃　        　　┏┛┆
┆　　┗┓┓┏━┳┓┏┛ ┆
┆　　　┃┫┫　┃┫┫ ┆
┆　　　┗┻┛　┗┻┛ ┆
************************************************ */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#define ll long long
using namespace std;
ll sum[55][55][55];
int n,m,K,q;
bool Map[55][55];
int num[55],d[55];
const ll mod=998244353;

bool cheak(int i,int j,int l)
{
    if(num[i]-num[j]>K||num[j]-num[i]>K) return false ;
    if(num[i]-num[l]>K||num[l]-num[i]>K) return false ;
    if(num[l]-num[j]>K||num[j]-num[l]>K) return false ;
    return true ;
}

int Abs(int i)
{
    if(i<0) i=-i;
    return i;
}

ll dfs(int i,int j,int k)
{
    if(sum[i][j][k]>=0) return sum[i][j][k];
    ll ans=0;
    for(int ii=1; ii<=n; ii++)
    {
        if(Map[i][ii])
        {
            for(int jj=1; jj<=n; jj++)
            {
                if(Map[j][jj]&&Abs(num[ii]-num[jj])<=K)
                {
                    for(int l=1; l<=n; l++)
                    {
                        if(Map[k][l]&&cheak(ii,jj,l))
                        {
                            ans=(ans+dfs(ii,jj,l))%mod;
                        }
                    }
                }
            }
        }
    }
    sum[i][j][k]=(ans+1)%mod;
    return (ans+1)%mod;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&K,&q);
        for(int i=1; i<=n; i++) scanf("%d",&num[i]);
        memset(sum,-1,sizeof(sum));
        memset(Map,false ,sizeof(Map));
        memset(d,0,sizeof(d));
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            Map[u][v]=true;
            d[v]++;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(Abs(num[i]-num[j])<=K)
                    for(int k=1; k<=n; k++)
                        if(cheak(i,j,k))
                            sum[i][j][k]=dfs(i,j,k);

        for(int i=0; i<q; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            printf("%d\n",sum[a][b][c]);
        }
    }
    return 0;
}

hdu Keep In Touch

原文：http://blog.csdn.net/u013097262/article/details/52138463

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)