1090 危险品装箱 (25 分)

捕获.PNG

解题思路:

首先我想到的是用一个足够大的动态二维数组来记录不相容的物品,行号代表该物品的编号,该列中存储与该物品不相容的其它物品

然后定义一个足够大的数组dir[100000],数组下标表示该物品的编号,元素值表示与该物品不相容的物品是否存在(数组初始值为零)

对集装箱的物品进行输入时每输入一个物品就将与该物品不相容的物品的值改为1,表示该物品已经存在。

每次输入物品good的时候就判断下dir[good]是否为1

#include <iostream>
#include<vector>
using namespace std;
vector<vector<int>> diss(100000, vector<int>(0));
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		int good1, good2;
		cin >> good1 >> good2;
		diss[good1].push_back(good2);
		diss[good2].push_back(good1);
	}
	for (int i = 0;i < m;i++) {
		int dir[100000] = { 0 };
		int k;
		cin >> k;
		bool flag = true;
		for (int j = 0;j < k;j++) {
			int good;
			cin >> good;
			if (dir[good] == 1&&flag) {
				cout << "No" << endl;
				flag = false;
			}
			for (int x = 0;x < diss[good].size();x++) {
				int ex = diss[good][x];
				dir[ex] = 1;
			}
		}
		if (flag) {
			cout << "Yes" << endl;
		}
	}
	return 0;
}
原文地址:https://www.cnblogs.com/chance-zou/p/10472139.html