PAT Basic Level 1090 危險品裝箱 解題思路及AC代碼 v1.0

PAT 乙級 1090 危險品裝箱

• • 1. 題目簡述及線上測試位置
  • 2. 基本思路
  • 3. 完整AC代碼

1. 題目簡述及線上測試位置

1.1 已知一系列的不相容物品（若A B放到一起，會觸發爆炸），給定N批不同種類的物品，判定是否會觸發爆炸

1.2 線上測試位置： 1090 危險品裝箱

2. 基本思路

2.1 本質是圖問題：物品可以抽象為圖的頂點，不相容物品 可以抽象為 這兩個頂點之間存在一條邊

2.2 根據輸入資料建圖：由于頂點範圍是(0,100000)，導緻無法使用鄰接矩陣（二維數組），是以采用鄰接表進行資料的存儲。對于本題，實際上隻需要建立圖的頭節點及鄰接點就可以了

#define MAX 100000

typedef struct AdjNode* PtrNode;
struct AdjNode
{
	int ID;
	PtrNode Next;
};

struct HeadNode //頭結點
{
	PtrNode PtrN; //鄰接點
};

struct HeadNode* Head;
Head = (struct HeadNode*)malloc(sizeof(struct HeadNode) * MAX);
           

2.3 将頂點之間的關系存入鄰接表後，對待判定的資料（也就是一系列的圖頂點）進行判定：若發現任意倆倆頂點之間存在邊，則不可以裝在一個箱子；反之，可以裝在一個箱子

3. 完整AC代碼

#include <stdlib.h>
#include <iostream>
using namespace std;

#define MAX 100000

typedef struct AdjNode* PtrNode;
struct AdjNode
{
	int ID;
	PtrNode Next;
};

struct HeadNode
{
	PtrNode PtrN; //鄰接點
};

struct HeadNode* Head;

bool Search(int HNode, int Node);
void Insert(int Node1, int Node2);

int main()
{
	
	Head = (struct HeadNode*)malloc(sizeof(struct HeadNode) * MAX);

	for (int i = 0; i < MAX; i++) //初始化圖的頭節點
		Head[i].PtrN = NULL;

	int Pair, Pieces; //倆倆關系數  待檢查的物品批次
	cin >> Pair >> Pieces;

	int Node1, Node2;
	for (int i = 0; i < Pair; i++) //将倆倆關系存入鄰接表
	{
		cin >> Node1 >> Node2;
		Insert(Node1, Node2);
		Insert(Node2, Node1);		
	}

	int N,Data;
	for (int p = 0; p < Pieces; p++)
	{
		cin >> N;
		int *a = (int*)malloc(sizeof(int) * N);
		for (int i = 0; i < N; i++)
		{
			cin >> Data;
			a[i] = Data;
		}

		int i;
		for (i = 0; i < N; i++)
		{
			int j;
			for (j = i + 1; j < N; j++) //檢查任意兩個頂點是否存在邊
			{
				if ( Search(a[i], a[j]) ) //若兩個頂點存在邊，則不安全
				{
					cout << "No" << endl;
					break;
				}
					
			}

			if (j < N)
				break;
		}
		if (i < N);
		else
			cout << "Yes" << endl;
			
	}	

	return 0;
}

bool Search(int HNode,int Node) //判定Node是否是頭結點HNode的鄰接點
{
	PtrNode PtrN;
	PtrN = Head[HNode].PtrN;
	while (PtrN != NULL)
	{
		
		if (PtrN->ID == Node)
		{
			return true; //
		}
		else
		{
			PtrN = PtrN->Next;
		}
	}
	return false;
}

void Insert(int HNode, int Node) //将節點Node插入頭結點HNode
{
	PtrNode PtrN ,tmp ;
	
	if (!Search(HNode, Node))
	{
		PtrN = (struct AdjNode*)malloc(sizeof(struct AdjNode));
		PtrN->ID = Node;
		PtrN->Next = NULL;

		tmp = Head[HNode].PtrN;
		Head[HNode].PtrN = PtrN;
		PtrN->Next = tmp;
	}
	return;
}