nbuoj 1537 Travel

[1537] Travel

时间限制: 2000 ms 内存限制: 65535 K
问题描述

One time, group master organized nekoTeam to travel, he always send a person to toilet before arriving a scene, and the rest of the people continued to move forward.
The scenes are numbered from 1 to n, nekoTeam was going from scene 1 to scene n.

输入

The first line contains an integer T, indicate the number of test cases.
The first line of each test case contains four integer: n m a b, separated by spaces (1 <= n, a, b <= 40), represents the number of scenes, paths, boys, girls.
The second line is string consists of n characters, the i-th character indicate the toilet type of the i-th scene, ‘A’ for men’s room, ‘B’ for women’s room.
The next m lines each contains two positive integers u v, indicate there is a two-way path between scene u and scene v. There is no multiple-paths and self-paths

输出

For each test case, if anyone can go to senario n, output “yes”, otherwise “no”.

样例输入

3
3 2 2 1
AAB
1 2
2 3
3 2 1 2
AAB
1 2
2 3
2 1 1 1
AA
1 2

样例输出

yes
no
no

 

  题意和思路:n,m,a,b分别代表场景数,道路数,男孩数量和女孩数量,下面是一个有n个字符的字符串str,’A’代表男洗手间,’B’代表女洗手间。下面的m行是路径,问按照题目所给的走的标准走,能不能从1走到n。

        把左右的路径标记到一个邻接矩阵里面,有路径的标为1,没有的就为0,利用广搜,把结果更新到dist数组里面,最后看看dist得到的值能不能满足str所给的顺序。dist里面始终存小的值。具体如下:

  1 /*
  2 ID: asif
  3 LANG: C++
  4 TASK: test
  5 */
  6 //# pragma comment(linker, "/STACK:102400000,102400000")
  7 # include<iostream>
  8 # include<cstdio>
  9 # include<cstdlib>
 10 # include<cstring>
 11 # include<algorithm>
 12 # include<cctype>
 13 # include<cmath>
 14 # include<string>
 15 # include<set>
 16 # include<map>
 17 # include<stack>
 18 # include<queue>
 19 # include<vector>
 20 # include<numeric>
 21 using namespace std;
 22 const int maxn=44;
 23 const double inf=0.000001;
 24 const int INF=~0U>>1;
 25 const int mod=1000000007;
 26 # define lson l,m,rt<<1
 27 # define rson m+1,r,rt<<1 | 1
 28 # define PS printf("
")
 29 # define S(n) scanf("%d",&n)
 30 # define P(n) printf("%d
",n)
 31 # define Ps(n) printf(" %d",(n))
 32 # define SB(n) scanf("%lld",&n)
 33 # define PB(n) printf("%lld
",n)
 34 # define PBs(n) printf(" %lld",n)
 35 # define SD(n) scanf("%lf",&n)
 36 # define PD(n) printf("%.3lf
",n)
 37 # define Sstr(s) scanf("%s",s)
 38 # define Pstr(s) printf("%s
",s)
 39 # define S0(a) memset(a,0,sizeof(a))
 40 # define S1(a) memset(a,-1,sizeof(a))
 41 typedef long long ll;
 42 int n,m,a,b,edge[maxn][maxn],dist[maxn][maxn][2],flag;
 43 char str[maxn];
 44 struct node
 45 {
 46     int x;
 47     int y;
 48     int suma;
 49     int sumb;
 50 };
 51 void bfs()
 52 {
 53     node s,t;
 54     s.x=0;
 55     s.y=0;
 56     if(str[0]=='A')
 57     {
 58         s.suma=1,s.sumb=0;
 59         for(int i=0;i<n;i++)
 60             if(edge[i][0])
 61             dist[i][0][0]=1,dist[i][0][1]=0;
 62     }
 63     else
 64     {
 65         s.suma=0,s.sumb=1;
 66         for(int i=0;i<n;i++)
 67             if(edge[i][0])
 68             dist[i][0][1]=1,dist[i][0][0]=0;
 69     }
 70     queue<node>q;
 71     q.push(s);
 72     while(!q.empty())
 73     {
 74         t=q.front();
 75         q.pop();
 76         for(int i=0;i<n;i++)
 77         {
 78             if(edge[t.x][i])
 79             {
 80                 s.x=i;
 81                 if(str[i]=='A')
 82                     s.suma=t.suma+1,s.sumb=t.sumb;
 83                 else
 84                     s.suma=t.suma,s.sumb=t.sumb+1;
 85                 if(s.suma<dist[t.x][s.x][0]||s.sumb<dist[t.x][s.x][1])//确保是没有查询过的点,不加会超时
 86                 {
 87                     dist[t.x][s.x][0]=min(dist[t.x][s.x][0],s.suma);
 88                     dist[t.x][s.x][1]=min(dist[t.x][s.x][1],s.sumb);
 89                     if(s.x==n-1)
 90                     {
 91                         if(a>=s.suma&&b>=s.sumb)//找到符合条件的就退出
 92                         {
 93                             flag=1;
 94                             return;
 95                         }
 96                     }
 97                     q.push(s);
 98                 }
 99             }
100         }
101     }
102 }
103 int main()
104 {
105     //freopen("input.in", "r", stdin);
106     //freopen("output.out", "w", stdout);
107     int T;
108     S(T);
109     while(T--)
110     {
111         scanf("%d%d%d%d",&n,&m,&a,&b);
112         S0(edge);
113         for(int i=0;i<maxn;i++)
114             for(int j=0;j<maxn;j++)
115                 dist[i][j][0]=dist[i][j][1]=INF;
116         Sstr(str);
117         for(int i=0;i<m;i++)
118         {
119             int u,v;
120             S(u),S(v);
121             u--,v--;
122             edge[u][v]=edge[v][u]=1;
123         }
124         flag=0;
125         bfs();
126         if(flag)
127             puts("yes");
128         else
129             puts("no");
130     }
131     return 0;
132 }

View Code

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注