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就可以过(注意输入内面狗子描述的是自身的时猴要特殊处理!因为这个wa了一次)

Posted by KatrineYang at 2016-08-21 02:59:19 on Problem 1291
#include <iostream>
#include <stdio.h>
using namespace std;

int adj[1004][1004];
bool adjTF[1004][1004];
int adjNum[1004];
int used[1004];

int dui, cuo;
int zong = 0;

void init(int N){
	for(int i = 1; i <= N; i++) {
		adjNum[i] = 0;
		used[i] = 0;
	}
	zong = 0;
}

void dfs(int i, bool tag){
	used[i] = tag?1:-1;
	if(tag) dui++;
	else cuo++;
	for(int j = 0; j < adjNum[i]; j++){
		if(used[adj[i][j]] == 0){
			bool t = (tag + adjTF[i][j])%2;
			dfs(adj[i][j], t);
		}
	}
}

int main() {
	while(1){
		int N;
		scanf("%d", &N);
		if(N == 0) break;
		init(N);
		char fei1[32], fei2[4];
		for(int i = 1; i <= N; i++){
			int j;
			char tf[15];
			scanf("%s%d%s%s", fei1, &j, fei2, tf);
			if(i != j){
				adj[i][adjNum[i]] = j;
				adj[j][adjNum[j]] = i;
				if(tf[0] == 't'){
					adjTF[i][adjNum[i]] = 0;
					adjTF[j][adjNum[j]] = 0;
				}
				else{
					adjTF[i][adjNum[i]] = 1;
					adjTF[j][adjNum[j]] = 1;
				}
				adjNum[i]++;
				adjNum[j]++;
			}
			else{
				adj[i][adjNum[i]] = i;
				if(tf[0] == 't'){
					adjTF[i][adjNum[i]] = 0;
				}
				else{
					adjTF[i][adjNum[i]] = 1;
				}
				adjNum[i]++;
			}
		}
		for(int i = 1; i <= N; i++){
			if(used[i] != 0) continue;
			dui = 0;
			cuo = 0;
			dfs(i, 1);
			if(dui > cuo) zong += dui;
			else zong += cuo;
		}
		bool ok = 1;
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < adjNum[i]; j++){
				if(adjTF[i][j] && used[i] == used[adj[i][j]]){
					ok = 0;
					break;
				}
				if(!adjTF[i][j] && used[i] != used[adj[i][j]]){
					ok = 0;
					break;
				}
			}
		}
		if(ok){
			printf("%d\n", zong);
		}
		else{
			printf("Inconsistent\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