古代符文路径的激活
题意
有 块符文石线性排列（编号
到
），每块石头上有若干铭文（编号各不相同，最大
）。石头之间有能量桥连接特定铭文，同一石头内部有灵脉连接两个铭文。
要找一条从符文石 到符文石
的"最和谐"激活路径。路径在每块石头上选定一个输入铭文
和一个输出铭文
（必须不同），通过灵脉从
流向
，再通过能量桥流入下一块石头。
灵脉的使用规则：
- 已有灵脉可以直接使用
- 新灵脉只能在两个未被占用的铭文之间创建（"未被占用"指不是任何已有灵脉的端点）
和谐度比较： 逐石比较评分三元组 ，其中
表示使用已有灵脉，
表示新建灵脉。字典序更小的更优。
，
。
思路
这题看起来复杂，但数据范围很小（，铭文编号
），暴力枚举完全可行。关键是要正确理解三个规则。
灵脉的合法性判断
先搞清楚在石头 上，一对
什么时候合法：
？ 不行。灵脉连接的是两个不同的铭文。
- 已有灵脉连接
和
？ 合法，
。
- 否则，
。
- 其他情况？ 不合法。因为已占用的铭文不能创建新灵脉。
两阶段算法
有了合法性判断，整体算法分两步：
第一步：反向可达性分析。 从最后一块石头开始，往前推导每块石头上哪些铭文作为 可以到达终点。
- 最后一块石头：
- 中间石头
：
合法，当且仅当存在
使得
合法，且
有能量桥通向石头
的某个可达铭文。
第二步：正向贪心选择。 从石头 开始，维护当前所有可能的
候选集。在每块石头上：
- 枚举所有
对，计算三元组。
- 选字典序最小的三元组。
- 由于三元组唯一确定了
第二维
），但可能有多条能量桥通向下一块石头的不同铭文。把这些下一步的
为什么贪心正确？因为只要当前石头的三元组分出了优劣，后续石头的选择就不影响比较了。相同三元组意味着到这一步为止路径等价，所以保留所有可能继续往下选就行。
时间复杂度 ，其中
是每块石头的能量桥数量，完全在约束范围内。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<vector<int>> inscriptions(N);
vector<set<int>> inscSet(N);
vector<set<pair<int,int>>> leyLines(N);
vector<set<int>> occupied(N);
vector<map<int, vector<int>>> bridgesByFrom(max(N-1, 0));
string line;
getline(cin, line);
for(int i = 0; i < N; i++){
getline(cin, line);
{
istringstream iss(line);
int x;
while(iss >> x){
inscriptions[i].push_back(x);
inscSet[i].insert(x);
}
}
getline(cin, line);
{
istringstream iss(line);
string tok;
while(iss >> tok){
if(tok == "0") break;
int pos = tok.find('-');
int a = stoi(tok.substr(0, pos));
int b = stoi(tok.substr(pos+1));
leyLines[i].insert({min(a,b), max(a,b)});
occupied[i].insert(a);
occupied[i].insert(b);
}
}
if(i < N-1){
getline(cin, line);
istringstream iss(line);
string tok;
while(iss >> tok){
if(tok == "0") break;
int pos = tok.find('-');
int a = stoi(tok.substr(0, pos));
int b = stoi(tok.substr(pos+1));
bridgesByFrom[i][a].push_back(b);
}
}
}
auto getIsNew = [&](int i, int pIn, int pOut) -> int {
if(pIn == pOut) return -1;
int a = min(pIn, pOut), b = max(pIn, pOut);
if(leyLines[i].count({a, b})) return 0;
if(!occupied[i].count(pIn) && !occupied[i].count(pOut)) return 1;
return -1;
};
if(N == 1){
tuple<int,int,int> best = {2, INT_MAX, INT_MAX};
int bpIn = -1, bpOut = -1;
for(int a : inscriptions[0])
for(int b : inscriptions[0]){
int isn = getIsNew(0, a, b);
if(isn < 0) continue;
auto t = make_tuple(isn, a+b, a);
if(t < best){ best = t; bpIn = a; bpOut = b; }
}
if(bpIn == -1) cout << -1 << endl;
else cout << bpIn << " " << bpOut << endl;
return 0;
}
// 反向可达性
vector<set<int>> reachable(N);
for(int x : inscriptions[N-1])
for(int y : inscriptions[N-1])
if(getIsNew(N-1, x, y) >= 0){ reachable[N-1].insert(x); break; }
for(int i = N-2; i >= 0; i--){
set<int> validPout;
for(auto& [a, bs] : bridgesByFrom[i]){
if(!inscSet[i].count(a)) continue;
for(int b : bs)
if(reachable[i+1].count(b)){ validPout.insert(a); break; }
}
for(int x : inscriptions[i])
for(int pOut : validPout)
if(getIsNew(i, x, pOut) >= 0){ reachable[i].insert(x); break; }
}
if(reachable[0].empty()){ cout << -1 << endl; return 0; }
// 正向贪心
set<int> curCands(reachable[0]);
vector<int> path;
for(int i = 0; i < N; i++){
bool isLast = (i == N-1);
tuple<int,int,int> bestT = {2, INT_MAX, INT_MAX};
struct Ch { int pIn, pOut, nxt; };
vector<Ch> choices;
for(int pIn : curCands){
if(!inscSet[i].count(pIn)) continue;
if(isLast){
for(int pOut : inscriptions[i]){
int isn = getIsNew(i, pIn, pOut);
if(isn < 0) continue;
auto t = make_tuple(isn, pIn+pOut, pIn);
if(t <= bestT){ if(t < bestT) bestT = t; choices.push_back({pIn, pOut, -1}); }
}
} else {
for(auto& [bA, bs] : bridgesByFrom[i]){
int pOut = bA;
if(!inscSet[i].count(pOut)) continue;
int isn = getIsNew(i, pIn, pOut);
if(isn < 0) continue;
auto t = make_tuple(isn, pIn+pOut, pIn);
for(int b : bs){
if(!reachable[i+1].count(b)) continue;
if(t <= bestT){ if(t < bestT) bestT = t; choices.push_back({pIn, pOut, b}); }
}
}
}
}
set<int> nxtCands;
int cPIn = -1, cPOut = -1;
for(auto& c : choices){
int isn = getIsNew(i, c.pIn, c.pOut);
if(make_tuple(isn, c.pIn+c.pOut, c.pIn) == bestT){
cPIn = c.pIn; cPOut = c.pOut;
if(!isLast) nxtCands.insert(c.nxt);
}
}
if(cPIn == -1){ cout << -1 << endl; return 0; }
path.push_back(cPIn); path.push_back(cPOut);
curCands = nxtCands;
}
for(int i = 0; i < (int)path.size(); i++){
if(i) cout << " ";
cout << path[i];
}
cout << endl;
}
import java.util.*;
import java.io.*;
public class Main {
static List<Set<Integer>> leyLinesSets, occupiedSets;
static int getIsNew(int i, int pIn, int pOut) {
if (pIn == pOut) return -1;
int a = Math.min(pIn, pOut), b = Math.max(pIn, pOut);
if (leyLinesSets.get(i).contains(a * 100 + b)) return 0;
if (!occupiedSets.get(i).contains(pIn) && !occupiedSets.get(i).contains(pOut)) return 1;
return -1;
}
static int cmp(int[] a, int[] b) {
for (int i = 0; i < 3; i++)
if (a[i] != b[i]) return Integer.compare(a[i], b[i]);
return 0;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine().trim());
List<int[]> inscriptions = new ArrayList<>();
List<Set<Integer>> inscSets = new ArrayList<>();
leyLinesSets = new ArrayList<>();
occupiedSets = new ArrayList<>();
List<Map<Integer, List<Integer>>> bridgesByFrom = new ArrayList<>();
for (int i = 0; i < N; i++) {
String[] parts = br.readLine().trim().split("\\s+");
int[] insc = new int[parts.length];
Set<Integer> s = new HashSet<>();
for (int j = 0; j < parts.length; j++) { insc[j] = Integer.parseInt(parts[j]); s.add(insc[j]); }
inscriptions.add(insc); inscSets.add(s);
String leyLine = br.readLine().trim();
Set<Integer> ll = new HashSet<>(), occ = new HashSet<>();
if (!leyLine.equals("0"))
for (String l : leyLine.split("\\s+")) {
String[] ab = l.split("-");
int a = Integer.parseInt(ab[0]), b = Integer.parseInt(ab[1]);
ll.add(Math.min(a,b)*100+Math.max(a,b)); occ.add(a); occ.add(b);
}
leyLinesSets.add(ll); occupiedSets.add(occ);
Map<Integer, List<Integer>> bf = new HashMap<>();
if (i < N - 1) {
String bl = br.readLine().trim();
if (!bl.equals("0"))
for (String b : bl.split("\\s+")) {
String[] ab = b.split("-");
int from = Integer.parseInt(ab[0]), to = Integer.parseInt(ab[1]);
bf.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
}
}
bridgesByFrom.add(bf);
}
if (N == 1) {
int[] best = {2, Integer.MAX_VALUE, Integer.MAX_VALUE};
int bpIn = -1, bpOut = -1;
for (int a : inscriptions.get(0)) for (int b : inscriptions.get(0)) {
int isn = getIsNew(0, a, b); if (isn < 0) continue;
int[] t = {isn, a+b, a};
if (cmp(t, best) < 0) { best = t; bpIn = a; bpOut = b; }
}
System.out.println(bpIn == -1 ? "-1" : bpIn + " " + bpOut);
return;
}
List<Set<Integer>> reachable = new ArrayList<>();
for (int i = 0; i < N; i++) reachable.add(new HashSet<>());
for (int x : inscriptions.get(N-1))
for (int y : inscriptions.get(N-1))
if (getIsNew(N-1, x, y) >= 0) { reachable.get(N-1).add(x); break; }
for (int i = N-2; i >= 0; i--) {
Set<Integer> vp = new HashSet<>();
for (var e : bridgesByFrom.get(i).entrySet()) {
if (!inscSets.get(i).contains(e.getKey())) continue;
for (int b : e.getValue()) if (reachable.get(i+1).contains(b)) { vp.add(e.getKey()); break; }
}
for (int x : inscriptions.get(i))
for (int p : vp) if (getIsNew(i, x, p) >= 0) { reachable.get(i).add(x); break; }
}
if (reachable.get(0).isEmpty()) { System.out.println(-1); return; }
Set<Integer> cur = new HashSet<>(reachable.get(0));
List<Integer> path = new ArrayList<>();
for (int i = 0; i < N; i++) {
boolean isLast = (i == N-1);
int[] bestT = {2, Integer.MAX_VALUE, Integer.MAX_VALUE};
List<int[]> choices = new ArrayList<>();
for (int pIn : cur) {
if (!inscSets.get(i).contains(pIn)) continue;
if (isLast) {
for (int pOut : inscriptions.get(i)) {
int isn = getIsNew(i, pIn, pOut); if (isn < 0) continue;
int[] t = {isn, pIn+pOut, pIn};
if (cmp(t, bestT) <= 0) { if (cmp(t, bestT) < 0) bestT = t; choices.add(new int[]{pIn, pOut, -1}); }
}
} else {
for (var e : bridgesByFrom.get(i).entrySet()) {
int pOut = e.getKey();
if (!inscSets.get(i).contains(pOut)) continue;
int isn = getIsNew(i, pIn, pOut); if (isn < 0) continue;
int[] t = {isn, pIn+pOut, pIn};
for (int b : e.getValue()) {
if (!reachable.get(i+1).contains(b)) continue;
if (cmp(t, bestT) <= 0) { if (cmp(t, bestT) < 0) bestT = t; choices.add(new int[]{pIn, pOut, b}); }
}
}
}
}
Set<Integer> nxt = new HashSet<>(); int cP = -1, cO = -1;
for (int[] c : choices) {
int isn = getIsNew(i, c[0], c[1]);
if (cmp(new int[]{isn, c[0]+c[1], c[0]}, bestT) == 0) {
cP = c[0]; cO = c[1]; if (!isLast) nxt.add(c[2]);
}
}
if (cP == -1) { System.out.println(-1); return; }
path.add(cP); path.add(cO); cur = nxt;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append(' '); sb.append(path.get(i)); }
System.out.println(sb);
}
}
import sys
input = sys.stdin.readline
def main():
N = int(input())
inscriptions, insc_sets, ley_lines, occupied_sets, bridges_by_from = [], [], [], [], []
for i in range(N):
parts = list(map(int, input().split()))
inscriptions.append(parts)
insc_sets.append(set(parts))
ley_tok = input().split()
ll, occ = set(), set()
if ley_tok[0] != '0':
for item in ley_tok:
a, b = map(int, item.split('-'))
ll.add((min(a,b), max(a,b)))
occ.add(a); occ.add(b)
ley_lines.append(ll); occupied_sets.append(occ)
bf = {}
if i < N - 1:
btok = input().split()
if btok[0] != '0':
for item in btok:
a, b = map(int, item.split('-'))
bf.setdefault(a, []).append(b)
bridges_by_from.append(bf)
def get_is_new(i, pin, pout):
if pin == pout: return -1
if (min(pin,pout), max(pin,pout)) in ley_lines[i]: return 0
if pin not in occupied_sets[i] and pout not in occupied_sets[i]: return 1
return -1
if N == 1:
best, bp, bo = (2, float('inf'), float('inf')), -1, -1
for a in inscriptions[0]:
for b in inscriptions[0]:
isn = get_is_new(0, a, b)
if isn < 0: continue
t = (isn, a+b, a)
if t < best: best, bp, bo = t, a, b
print(-1 if bp == -1 else f"{bp} {bo}")
return
reachable = [set() for _ in range(N)]
for x in inscriptions[N-1]:
for y in inscriptions[N-1]:
if get_is_new(N-1, x, y) >= 0:
reachable[N-1].add(x); break
for i in range(N-2, -1, -1):
vp = set()
for a, bs in bridges_by_from[i].items():
if a not in insc_sets[i]: continue
for b in bs:
if b in reachable[i+1]: vp.add(a); break
for x in inscriptions[i]:
for p in vp:
if get_is_new(i, x, p) >= 0: reachable[i].add(x); break
if not reachable[0]: print(-1); return
cur, path = set(reachable[0]), []
for i in range(N):
is_last = (i == N-1)
best_t, choices = (2, float('inf'), float('inf')), []
for pin in cur:
if pin not in insc_sets[i]: continue
if is_last:
for pout in inscriptions[i]:
isn = get_is_new(i, pin, pout)
if isn < 0: continue
t = (isn, pin+pout, pin)
if t <= best_t:
if t < best_t: best_t = t
choices.append((pin, pout, -1))
else:
for ba, bs in bridges_by_from[i].items():
if ba not in insc_sets[i]: continue
isn = get_is_new(i, pin, ba)
if isn < 0: continue
t = (isn, pin+ba, pin)
for b in bs:
if b not in reachable[i+1]: continue
if t <= best_t:
if t < best_t: best_t = t
choices.append((pin, ba, b))
nxt, cp, co = set(), -1, -1
for c in choices:
isn = get_is_new(i, c[0], c[1])
if (isn, c[0]+c[1], c[0]) == best_t:
cp, co = c[0], c[1]
if not is_last: nxt.add(c[2])
if cp == -1: print(-1); return
path += [cp, co]; cur = nxt
print(' '.join(map(str, path)))
main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
let idx = 0;
const N = parseInt(lines[idx++]);
const inscriptions = [], inscSets = [], leyLines = [], occupied = [], bridgesByFrom = [];
for (let i = 0; i < N; i++) {
const parts = lines[idx++].split(/\s+/).map(Number);
inscriptions.push(parts); inscSets.push(new Set(parts));
const leyParts = lines[idx++].split(/\s+/);
const ll = new Set(), occ = new Set();
if (leyParts[0] !== '0')
for (const item of leyParts) {
const [a, b] = item.split('-').map(Number);
ll.add(Math.min(a,b)*100+Math.max(a,b)); occ.add(a); occ.add(b);
}
leyLines.push(ll); occupied.push(occ);
const bf = new Map();
if (i < N - 1) {
const bParts = lines[idx++].split(/\s+/);
if (bParts[0] !== '0')
for (const item of bParts) {
const [a, b] = item.split('-').map(Number);
if (!bf.has(a)) bf.set(a, []);
bf.get(a).push(b);
}
}
bridgesByFrom.push(bf);
}
const getIsNew = (i, pIn, pOut) => {
if (pIn === pOut) return -1;
const a = Math.min(pIn, pOut), b = Math.max(pIn, pOut);
if (leyLines[i].has(a*100+b)) return 0;
if (!occupied[i].has(pIn) && !occupied[i].has(pOut)) return 1;
return -1;
};
const cmpT = (a, b) => { for (let k = 0; k < 3; k++) if (a[k] !== b[k]) return a[k]-b[k]; return 0; };
if (N === 1) {
let best = [2, 1e9, 1e9], bp = -1, bo = -1;
for (const a of inscriptions[0]) for (const b of inscriptions[0]) {
const isn = getIsNew(0, a, b); if (isn < 0) continue;
const t = [isn, a+b, a];
if (cmpT(t, best) < 0) { best = t; bp = a; bo = b; }
}
console.log(bp === -1 ? "-1" : bp + " " + bo); return;
}
const reachable = []; for (let i = 0; i < N; i++) reachable.push(new Set());
for (const x of inscriptions[N-1])
for (const y of inscriptions[N-1])
if (getIsNew(N-1, x, y) >= 0) { reachable[N-1].add(x); break; }
for (let i = N-2; i >= 0; i--) {
const vp = new Set();
for (const [a, bs] of bridgesByFrom[i]) {
if (!inscSets[i].has(a)) continue;
for (const b of bs) if (reachable[i+1].has(b)) { vp.add(a); break; }
}
for (const x of inscriptions[i])
for (const p of vp) if (getIsNew(i, x, p) >= 0) { reachable[i].add(x); break; }
}
if (reachable[0].size === 0) { console.log(-1); return; }
let cur = new Set(reachable[0]);
const path = [];
for (let i = 0; i < N; i++) {
const isLast = (i === N-1);
let bestT = [2, 1e9, 1e9];
const choices = [];
for (const pIn of cur) {
if (!inscSets[i].has(pIn)) continue;
if (isLast) {
for (const pOut of inscriptions[i]) {
const isn = getIsNew(i, pIn, pOut); if (isn < 0) continue;
const t = [isn, pIn+pOut, pIn];
if (cmpT(t, bestT) <= 0) { if (cmpT(t, bestT) < 0) bestT = t; choices.push([pIn, pOut, -1]); }
}
} else {
for (const [bA, bs] of bridgesByFrom[i]) {
if (!inscSets[i].has(bA)) continue;
const isn = getIsNew(i, pIn, bA); if (isn < 0) continue;
const t = [isn, pIn+bA, pIn];
for (const b of bs) {
if (!reachable[i+1].has(b)) continue;
if (cmpT(t, bestT) <= 0) { if (cmpT(t, bestT) < 0) bestT = t; choices.push([pIn, bA, b]); }
}
}
}
}
const nxt = new Set(); let cP = -1, cO = -1;
for (const c of choices) {
const isn = getIsNew(i, c[0], c[1]);
if (cmpT([isn, c[0]+c[1], c[0]], bestT) === 0) {
cP = c[0]; cO = c[1]; if (!isLast) nxt.add(c[2]);
}
}
if (cP === -1) { console.log(-1); return; }
path.push(cP, cO); cur = nxt;
}
console.log(path.join(' '));
});
复杂度
- 时间复杂度：
，其中
是符文石数量，
是最大铭文编号，
是单石最大能量桥数。
- 空间复杂度：
。
京公网安备 11010502036488号