解题思路

你要在食堂的菜品中各选出一份 全票菜（type=1）、半票菜（type=2）、素菜（type=3）， 要求这三份菜里出现的食材编号不能有重复。每个菜最多 4 种食材，0 表示没有食材。

输入给出了 N 个菜： ID, T, D1, D2, D3, D4

• ID 为菜品编号
• T 为菜品类型 1/2/3
• D1..D4 为这道菜的食材编号（>0 有效，0 表示空）

输出：所有满足要求的三菜组合列表，每行 全票菜ID 半票菜ID 素菜ID 排序规则为：

1. 先按全票菜 ID 升序
2. 若相同，再按半票菜 ID 升序
3. 若还相同，再按素菜 ID 升序 若不存在任何合法组合，输出 -1。

核心算法（暴力枚举 + 分类）

1. 读入所有菜品，按类型分成三组：full（全票）、half（半票）、veg（素菜）。

2. 对每个菜，只保留非 0 的食材，存成一个小数组 / 向量。

3. 暴力枚举三重循环：

   • 枚举全票菜 F
   • 枚举半票菜 H
   • 枚举素菜 V

4. 对当前三道菜，检查食材是否两两有交集：

   • 写一个函数 share(A, B)，如果两菜的任意一个食材编号相同，则返回 true。

   • 组合合法当且仅当：

     • !share(F, H) && !share(F, V) && !share(H, V)

5. 对于每个合法组合，把 (F.id, H.id, V.id) 加入答案数组。

6. 对答案数组按字典序排序（即按上面的三重关键字排序）。

7. 按顺序输出所有组合；若数组为空，输出 -1。

由于每道菜最多 4 个食材，检查两菜是否冲突最多比较 16 次，常数很小，直接暴力足够。

复杂度分析

设全票菜数量为 A，半票菜数量为 B，素菜数量为 C，总菜数 N ≤ 100。

• 三重枚举：O(A * B * C)，最坏情况下 A, B, C 都是 O(N)，复杂度 O(N^3)。
• 每次冲突检查是常数级（最多 16 次比较）。

所以总体时间复杂度 O(N^3)（这里 N ≤ 100，可以轻松通过）。 空间复杂度：只存菜品和所有答案，都是 O(N + 答案数量)，在数据范围内完全可行。

代码实现

Python

import sys

# 菜品结构：id, type, ingredients(只保存非0食材)
class Dish:
    def __init__(self, did, tp, ing):
        self.id = did
        self.tp = tp
        self.ing = ing

# 判断两道菜是否有相同食材
def share(d1, d2):
    for x in d1.ing:
        for y in d2.ing:
            if x == y:
                return True
    return False

# 核心功能：返回所有合法组合 (fid, hid, vid)
def solve(dishes):
    full = []
    half = []
    veg = []

    # 按类型分类
    for d in dishes:
        if d.tp == 1:
            full.append(d)
        elif d.tp == 2:
            half.append(d)
        elif d.tp == 3:
            veg.append(d)

    res = []

    # 三重枚举所有组合
    for f in full:
        for h in half:
            if share(f, h):  # 先剪枝：全票与半票冲突则跳过
                continue
            for v in veg:
                # 三两两不冲突才是合法组合
                if share(f, v) or share(h, v):
                    continue
                res.append((f.id, h.id, v.id))

    # 按 (全票ID, 半票ID, 素菜ID) 升序排序
    res.sort()
    return res

def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    it = iter(data)

    n = next(it)
    dishes = []

    # 读取所有菜品
    for _ in range(n):
        did = next(it)
        tp = next(it)
        tmp_ing = [next(it) for _ in range(4)]
        ing = [x for x in tmp_ing if x > 0]  # 去掉为0的占位
        dishes.append(Dish(did, tp, ing))

    ans = solve(dishes)

    out_lines = []
    if not ans:
        out_lines.append("-1\n")
    else:
        for fid, hid, vid in ans:
            out_lines.append(f"{fid} {hid} {vid}\n")

    sys.stdout.write("".join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.util.*;

// ACM 风格主类
public class Main {

    // 菜品结构
    static class Dish {
        int id;         // 菜品编号
        int type;       // 菜品类型 1/2/3
        int[] ing;      // 有效食材列表（不含0）

        Dish(int id, int type, int[] ing) {
            this.id = id;
            this.type = type;
            this.ing = ing;
        }
    }

    // 判断两道菜是否有相同食材
    static boolean share(Dish a, Dish b) {
        for (int x : a.ing) {
            for (int y : b.ing) {
                if (x == y) {
                    return true;
                }
            }
        }
        return false;
    }

    // 核心功能：返回所有合法组合
    static List<int[]> solve(List<Dish> dishes) {
        List<Dish> full = new ArrayList<>();
        List<Dish> half = new ArrayList<>();
        List<Dish> veg = new ArrayList<>();

        // 按类型分类
        for (Dish d : dishes) {
            if (d.type == 1) {
                full.add(d);
            } else if (d.type == 2) {
                half.add(d);
            } else if (d.type == 3) {
                veg.add(d);
            }
        }

        List<int[]> res = new ArrayList<>();

        // 三重枚举所有组合
        for (Dish f : full) {
            for (Dish h : half) {
                if (share(f, h)) { // 先检查这两道菜
                    continue;
                }
                for (Dish v : veg) {
                    if (share(f, v) || share(h, v)) {
                        continue;
                    }
                    res.add(new int[]{f.id, h.id, v.id});
                }
            }
        }

        // 按 (全票ID, 半票ID, 素菜ID) 排序
        Collections.sort(res, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                }
                if (a[1] != b[1]) {
                    return a[1] - b[1];
                }
                return a[2] - b[2];
            }
        });

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        if (!sc.hasNextInt()) {
            return; // 无输入直接结束
        }

        int n = sc.nextInt();
        List<Dish> dishes = new ArrayList<>();

        // 读取n个菜品
        for (int i = 0; i < n; i++) {
            int id = sc.nextInt();
            int type = sc.nextInt();
            int[] tmp = new int[4];
            for (int j = 0; j < 4; j++) {
                tmp[j] = sc.nextInt();
            }
            // 过滤掉0，只保留真正的食材
            int cnt = 0;
            for (int x : tmp) {
                if (x > 0) {
                    cnt++;
                }
            }
            int[] ing = new int[cnt];
            int idx = 0;
            for (int x : tmp) {
                if (x > 0) {
                    ing[idx++] = x;
                }
            }
            dishes.add(new Dish(id, type, ing));
        }

        List<int[]> ans = solve(dishes);

        if (ans.isEmpty()) {
            System.out.println("-1");
        } else {
            for (int[] arr : ans) {
                System.out.println(arr[0] + " " + arr[1] + " " + arr[2]);
            }
        }

        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 菜品结构体
struct Dish {
    int id;                 // 菜品编号
    int type;               // 菜品类型 1/2/3
    vector<int> ing;        // 食材列表（不含0）
};

// 判断两道菜是否有相同食材
bool share(const Dish &a, const Dish &b) {
    for (int x : a.ing) {
        for (int y : b.ing) {
            if (x == y) return true;
        }
    }
    return false;
}

// 核心功能：返回所有合法组合
vector<tuple<int,int,int>> solve(const vector<Dish> &dishes) {
    vector<Dish> full, half, veg;

    // 按类型分类
    for (const auto &d : dishes) {
        if (d.type == 1) full.push_back(d);
        else if (d.type == 2) half.push_back(d);
        else if (d.type == 3) veg.push_back(d);
    }

    vector<tuple<int,int,int>> res;

    // 三重枚举所有组合
    for (const auto &f : full) {
        for (const auto &h : half) {
            if (share(f, h)) continue; // 先剪枝
            for (const auto &v : veg) {
                if (share(f, v) || share(h, v)) continue;
                res.emplace_back(f.id, h.id, v.id);
            }
        }
    }

    // 默认按 (first, second, third) 字典序排序
    sort(res.begin(), res.end());
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0; // 无输入
    }

    vector<Dish> dishes;
    dishes.reserve(n);

    // 读取所有菜品
    for (int i = 0; i < n; ++i) {
        int id, type;
        cin >> id >> type;
        vector<int> ing;
        for (int j = 0; j < 4; ++j) {
            int x;
            cin >> x;
            if (x > 0) ing.push_back(x); // 丢弃0
        }
        dishes.push_back(Dish{id, type, ing});
    }

    vector<tuple<int,int,int>> ans = solve(dishes);

    if (ans.empty()) {
        cout << -1 << "\n";
    } else {
        for (auto &t : ans) {
            int fid, hid, vid;
            tie(fid, hid, vid) = t;
            cout << fid << " " << hid << " " << vid << "\n";
        }
    }

    return 0;
}

题目内容

你来到食堂想大吃一顿。你将在全荤、半荤、素中各挑选一种菜品，且所挑选菜品的食材不能重复，请你计算 菜品选择方式

输入描述

食堂的所有餐线的菜单 第$1$行是：$N$，其中$N$为所有菜品数量,范围$(0,100]$

第$2$行是：$ID_1\ T_1 \ DI_1\ DI_2\ DI_3\ DI_4$,其中$ID_1$:为第1个菜品的菜品名，范围$(0,100]$。$T_1$为菜品类型，$1$表示全荤、$2$表示半荤、$3$表示素。$DI_1...DI_4$分别为第$1$个菜品的第$1$种到第$4$种食材，食材不会重复,范围$[0,100]$，$0$表示占位，无食材。

第$N+1$行是:$ID_N\ T_N\ DN_1\ DN_2\ DN_3\ DN_4$，其中$ID_N$为第$N$个菜品的菜品名。$T_N$为菜品类型。$DN_1...DN_4$分别为第$N$个菜品的第$1$种到第$4$种食材

输出描述

菜品选择的所有方式列表，列表优先按照全荤菜品名升序排序，其次半荤菜品名升序排序，再次兼菜品名升序 排序 每行格式:全荤菜品名 半荤菜品名 素菜品名

无法选择请输出$-1$

样例1

输入

1
1 1 1 2 3 4

输出

-1

说明

仅有$1$个菜，无法按要求挑选

样例2

输入

6
2 2 5 6 7 8
3 3 9 10 11 12
4 2 1 2 3 0
5 1 5 0 7 8
1 1 1 2 3 4
6 1 1 2 3 4

输出

1 2 3
5 4 3
6 2 3

说明

总共有$6$种菜品。

菜品名$2$，半荤，食材$5、6、7、8$

菜品名$3$，素，食材$9、10、11、12$

菜品名$4$，半荤，食材$1、2、3$

菜品名$5$，全荤，食材$5、7、8$

菜品名$1$，全荤，食材$1、2、3、4$

菜品名$6$，全荤，食材$1、2、3、4$

菜品1、菜品4、菜品6食材有相同的部分，不能同时选择。

菜品2和菜品5食材有相同的部分，不能同时选择。

可选择的方式有$5+4+3,1+2+3,6+2+3$ $3$种。且根据升序排序要求输出 $1\ 2\ 3$ $5\ 4\ 3$ $6\ 2\ 3$

样例3

输入

4
1 1 1 2 3 4
2 2 5 6 7 8
3 3 9 10 11 12
4 2 13 14 15 16

输出

1 2 3
1 4 3

说明

总共有$4$种菜品

菜品名$1$，全荤，食材$1、2、3、4$

菜品名$2$，半荤，食材$5、6、7、8$

菜品名$3$，素，食材$9、10、11、12$

菜品名$4$，半荤，食材$13、14、15、16$

由于食材都不重复。

可选择的方式有$1+2+3,1+4+3$ $2$种

提示

由于中餐的博大精深。 同样的食材选择可做出不同的菜品。但同一个菜品名一定是同样的食材