首页 > ACM题库 > HDU-杭电 > HDU 3478-Catch[解题报告]HOJ
2014
04-04

HDU 3478-Catch[解题报告]HOJ

Catch

问题描述 :

A thief is running away!
We can consider the city where he locates as an undirected graph in which nodes stand for crosses and edges stand for streets. The crosses are labeled from 0 to N�1.
The tricky thief starts his escaping from cross S. Each moment he moves to an adjacent cross. More exactly, assume he is at cross u at the moment t. He may appear at cross v at moment t + 1 if and only if there is a street between cross u and cross v. Notice that he may not stay at the same cross in two consecutive moment.
The cops want to know if there’s some moment at which it’s possible for the thief to appear at any cross in the city.

输入:

The input contains multiple test cases:
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains three integers N (≤ 100 000), M (≤ 500 000), and S. N is the number of crosses. M is the number of streets and S is the index of the cross where the thief starts his escaping.
For the next M lines, there will be 2 integers u and v in each line (0 ≤ u, v < N). It means there’s an undirected street between cross u and cross v.

输出:

The input contains multiple test cases:
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains three integers N (≤ 100 000), M (≤ 500 000), and S. N is the number of crosses. M is the number of streets and S is the index of the cross where the thief starts his escaping.
For the next M lines, there will be 2 integers u and v in each line (0 ≤ u, v < N). It means there’s an undirected street between cross u and cross v.

样例输入:

2
3 3 0
0 1
0 2
1 2
2 1 0
0 1

样例输出:

Case 1: YES
Case 2: NO


Hint
For the first case, just look at the table below. (YES means the thief may appear at the cross at that moment)
Temperature
For the second input, at any moment, there’s at least one cross that the thief can’t reach.

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int inf = 0x3fffffff;
const int maxn=100005;
const int maxm=1000005;
struct data
{
	int to,nxt;
};
data e[maxm];
int head[maxn];
bool vis[maxn],ou[maxn],ji[maxn];
int num=0;
int n,m,s;
int cas=0;
void insert(int a,int b)
{
	e[num].to=b;
	e[num].nxt=head[a];
	head[a]=num++;
}
void process()
{
	ou[s]=1;
	for(int k=0;k<2;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=head[i];j!=-1;j=e[j].nxt)
			{
				int to=e[j].to;
				if(ou[i]) ji[to]=1;
				if(ji[i]) ou[to]=1;
			}
		}
	}
}
void check()
{
	int fo=1,fe=1;
		for(int i=0;i<n;i++)
		{
			if(!ji[i])fo=0;
			if(!ou[i])fe=0;
		}
		printf("Case %d: ",++cas);
		if(fo+fe==0)printf("NO\n");
		else printf("YES\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		memset(ou,0,sizeof(ou));
		memset(ji,0,sizeof(ji));
		num=0;
		scanf("%d%d%d",&n,&m,&s);
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			insert(a,b);
			insert(b,a);
		}
		process();
		check();
	}
}

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。