Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs,0ms秒杀,附代妈

Posted by KatrineYang at 2016-08-29 23:13:38 on Problem 1227
#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;

const int OU = 0, JI = 1;

int adjNo[105] = {0};
int adjList[105][105];

void dfs(int cur, bool *jiused, bool *ouused, int jiou){
	if(jiou == OU){
		ouused[cur] = 1;
		for(int i = 0; i < adjNo[cur]; i++){
			if(jiused[adjList[cur][i]]) continue;
			dfs(adjList[cur][i], jiused, ouused, JI);
		}
	}
	else{
		jiused[cur] = 1;
		for(int i = 0; i < adjNo[cur]; i++){
			if(ouused[adjList[cur][i]]) continue;
			dfs(adjList[cur][i], jiused, ouused, OU);
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for(int ii = 0; ii < T; ii++){
		int N, K;
		scanf("%d%d", &N, &K);
		map<int, int> bh;
		int cnt = 0;
		for(int i = 0; i < N; i++) adjNo[i] = 0;
		for(int i = 0; i < N; i++){
			int x, n, bhx;
			scanf("%d%d", &x, &n);
			if(bh.find(x) == bh.end()){
				bhx = cnt;
				bh.insert(pair<int, int>(x, cnt));
				cnt++;
			}
			else{
				bhx = bh[x];
			}
			adjNo[bhx] = n;
			for(int j = 0; j < n; j++){
				int id;
				scanf("%d", &id);
				int bhid;
				if(bh.find(id) == bh.end()){
					bhid = cnt;
					bh.insert(pair<int, int>(id, cnt));
					cnt++;
				}
				else{
					bhid = bh[id];
				}
				adjList[bhx][j] = bhid;
			}
		}

		int robotList[105];
		for(int i = 0; i < K; i++){
			int tmp;
			scanf("%d", &tmp);
			robotList[i] = bh[tmp];
		}
		if(K == 1){
			printf("YES\n");
			continue;
		}
		bool jiused[105] = {0}, ouused[105] = {0};
		dfs(robotList[0], jiused, ouused, OU);
		bool ok = 1;
		for(int i = 1; i < K; i++){
			if(!ouused[robotList[i]]){
				ok = 0;
				break;
			}
		}
		if(ok) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator