UVa12344 Jewel Transportation题目链接题意输入格式输出格式分析AC 代码题目链接UVA - 12344 Jewel Transportation题意一家富有的公司希望将 k 种珠宝从各自的工厂运送到目的地。不同珠宝的工厂和目的地可能不同。为了确保珠宝运输不受未知因素影响公司决定购买所有需要的道路并在每条道路上安装专门的运输设施。每条道路不能用于运输两种或两种以上的珠宝因此任意两种珠宝必须沿着两条边不相交的路径从各自的工厂运送到各自的目的地。请帮助公司最小化购买道路和安装设施的总费用。输入格式输入最多包含 10 组测试数据。每组测试数据包含三个整数 n, m, k1 ≤ n ≤ 161 ≤ m ≤ 1001 ≤ k ≤ 5分别表示城市数量、道路数量和珠宝种类数。接下来 m 行每行以两个不同的整数 a, b 开头随后是 k 个整数 ci1 ≤ ci ≤ 1000描述一条从城市 a 到城市 b 的有向道路如果为该道路安装运输第 i 种珠宝的设施则费用为 ci。城市编号为 1 到 n。最后 k 行每行描述一种珠宝包含两个整数 s 和 t分别表示该珠宝的工厂所在城市和目的地城市。最后一组测试数据后跟三个零表示输入结束不进行处理。输出格式对于每组测试数据在第一行输出最小总费用若无解输出 -1。若有解则再输出 k 行每行对应一种珠宝。每行的第一个整数为路径所用的道路数量随后列出这些道路的编号。道路按输入顺序编号为 1 到 m。分析典型的多商品流问题可以用线性规划的整数规划来求解暂未找到整数规划的模板自写算法难度较大。针对本题规模城市数 n ≤ 16珠宝种类 k ≤ 5道路数 m ≤ 100可以采用搜索减枝的方式求解。核心思路是 “带强剪枝的回溯搜索DFS”配合 “贪心求上界 启发式下界” 来进行加速。下面将求解思路拆解为 6 个关键步骤预处理计算每类珠宝的“乐观最短距离”下界基石对于每一种珠宝 i在原始全图不考虑边冲突上以它的目的地 t[i] 为起点反向跑一次 Dijkstra。得到数组 dist[i][v]表示从任意城市 v 到目的地 t[i] 的最短路径费用仅考虑该类珠宝的成本。作用在搜索过程中无论当前路径怎么走从当前点 u 到终点 t[i] 的剩余费用都不可能低于 dist[i][u]。这是一个极其有效的可采纳下界Admissible Heuristic。贪心获得一个“初始可行解”收紧上界在正式暴力搜索前先快速找一个不错的可行解把答案上界 bestCost 压下来。因为 k ≤ 5全排列只有 5! 120 种。枚举所有珠宝的处理顺序按该顺序依次做贪心每次选择当前珠宝时在尚未被占用的边上跑一次普通 Dijkstra或 BFS优先队列找一条从起点到终点的最短路径。占掉这条路径上的所有边累加费用。取这 120 种顺序中费用最小的方案作为初始 bestCost并记录对应路径。目的上界越紧后续搜索中剪枝掉的无效分支就越多。确定搜索顺序“困难优先”原则虽然贪心时试了所有排列但正式深度优先搜索DFS需要一个固定的处理顺序。策略将珠宝按照 dist[i][sr[i]]即起点到终点的乐观最短距离从大到小排序。直觉距离越远、约束越紧的珠宝先安排可以尽早发现冲突并回溯避免在容易的珠宝上浪费大量搜索时间。核心搜索DFS 逐类珠宝枚举“边不相交”路径这是算法的主体。DFS 的每一层负责为一类珠宝找一条路径。状态维护used一个 bitset记录当前已经被占用的道路编号。curCost当前已确定路径的总费用。paths已确定的各类珠宝路径。路径枚举关键对于当前珠宝 i从起点 sr[i] 出发利用递归enumPaths 函数枚举所有可能的简单路径不允许经过重复城市因为正权图最优路径必是简单路径用 mask 位记录访问过的城市防环。在枚举下一条边时必须跳过used 中已被占用的边以及当前路径已经走过的边。为了尽快找到好路径将当前节点的邻接边按照 dist[i][v]到达终点的剩余下界从小到大排序sortedAdj优先尝试最有希望的边。核心剪枝三重下界联合剪枝这是算法能在 n16, m100 下跑通的关键。在枚举路径的每一步计算pcost当前这条珠宝路径已花费的费用。dist[i][u]从当前点 u 到终点的剩余最短费用乐观估计remainAfter尚未处理的后续珠宝各自从起点到终点的乐观最短费用之和也忽略边冲突。如果满足以下不等式直接剪枝停止当前分支的延伸c u r C o s t p c o s t d i s t [ i ] [ u ] r e m a i n A f t e r ≥ b e s t C o s t curCostpcostdist[i][u]remainAfter≥bestCostcurCostpcostdist[i][u]remainAfter≥bestCost理由即使后面的边完全不冲突费用也不可能低于这个乐观估计。如果这都大于等于当前已知最优解那这个分支绝对不可能产生更优解。回溯与更新当一条珠宝的路径枚举完成到达终点 tr[i]将该路径的边并入 used进入下一层 DFS。当所有 k 类珠宝都安排完毕且 curCost bestCost则更新全局最优解 bestCost 并记录 bestPaths。搜索全部结束后若 bestCost 仍为无穷大输出 -1否则输出最小费用和路径。AC 代码#includebits/stdc.husingnamespacestd;constintINF1e9;constintMAXN16;constintMAXM100;constintMAXK5;structEdge{intu,v;intcost[MAXK];};intn,m,k;vectorEdgeedges;intsr[MAXK],tr[MAXK];intdist[MAXK][MAXN];// dist[i][v] min cost from v to tr[i]vectorvectorintadj;// original graph adjacency list (edge indices)vectorvectorpairint,intradj;// reverse graph: (from, edge_idx)vectorintsortedAdj[MAXK][MAXN];// sorted adjacency for each jewelry i and node ubitsetMAXMusedMask;vectorintorder;// jewelry processing orderintbestCostINF;vectorintbestPaths[MAXK];// ---------- Dijkstra for shortest path from every node to tr[i] ----------voiddijkstra(intidx){vectorintd(n,INF);priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;d[tr[idx]]0;pq.push({0,tr[idx]});while(!pq.empty()){auto[du,u]pq.top();pq.pop();if(du!d[u])continue;for(auto[v,e]:radj[u]){// reverse edge: original edge e: v - uif(d[v]duedges[e].cost[idx]){d[v]duedges[e].cost[idx];pq.push({d[v],v});}}}for(inti0;in;i)dist[idx][i]d[i];}// ---------- Greedy for a given order ----------boolgreedyForOrder(constvectorintord,inttotalCost,vectorintpaths[MAXK]){bitsetMAXMused;totalCost0;for(intidx:ord){intiidx;if(sr[i]tr[i]){paths[i].clear();continue;}vectorintd(n,INF),parent(n,-1),parentEdge(n,-1);priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;d[sr[i]]0;pq.push({0,sr[i]});while(!pq.empty()){auto[du,u]pq.top();pq.pop();if(du!d[u])continue;for(inte:adj[u]){if(used[e])continue;intvedges[e].v;if(d[v]duedges[e].cost[i]){d[v]duedges[e].cost[i];parent[v]u;parentEdge[v]e;pq.push({d[v],v});}}}if(d[tr[i]]INF)returnfalse;vectorintpath;intcurtr[i];while(cur!sr[i]){inteparentEdge[cur];path.push_back(e);used.set(e);curparent[cur];}reverse(path.begin(),path.end());paths[i]path;totalCostd[tr[i]];}returntrue;}// ---------- Initial upper bound by trying all permutations ----------voidgetInitialSolution(){vectorintperm(k);iota(perm.begin(),perm.end(),0);do{vectorinttmpPaths[MAXK];intcost;if(greedyForOrder(perm,cost,tmpPaths)){if(costbestCost){bestCostcost;for(inti0;ik;i)bestPaths[i]tmpPaths[i];}}}while(next_permutation(perm.begin(),perm.end()));}// ---------- DFS search ----------voidsearch(intidx,intcurCost,constbitsetMAXMused,constvectorintpaths[MAXK]);// Enumerate all simple paths for current jewelry ivoidenumPaths(inti,intidx,intcurCost,constbitsetMAXMused,constvectorintpaths[MAXK],bitsetMAXMpathMask,intu,intmask,intpcost,constvectorintpedges,intremainAfter){if(utr[i]){// Complete path for this jewelryvectorintnewPaths[MAXK];for(intj0;jk;j)newPaths[j]paths[j];newPaths[i]pedges;bitsetMAXMnewUsedused|pathMask;search(idx1,curCostpcost,newUsed,newPaths);return;}// Prune: current partial path lower bound of remaining part for this jewelry lower bound of later jewelryif(pcostdist[i][u]remainAfterbestCost)return;for(inte:sortedAdj[i][u]){intvedges[e].v;if(mask(1v))continue;if(used[e]||pathMask[e])continue;if(pcostedges[e].cost[i]dist[i][v]remainAfterbestCost)continue;bitsetMAXMnewPathMaskpathMask;newPathMask.set(e);vectorintnewPedgespedges;newPedges.push_back(e);enumPaths(i,idx,curCost,used,paths,newPathMask,v,mask|(1v),pcostedges[e].cost[i],newPedges,remainAfter);}}voidsearch(intidx,intcurCost,constbitsetMAXMused,constvectorintpaths[MAXK]){if(idxk){if(curCostbestCost){bestCostcurCost;for(inti0;ik;i)bestPaths[i]paths[i];}return;}intiorder[idx];// Lower bound for remaining jewelryintremain0;for(intjidx;jk;j){intidorder[j];remaindist[id][sr[id]];}if(curCostremainbestCost)return;if(sr[i]tr[i]){vectorintnewPaths[MAXK];for(intj0;jk;j)newPaths[j]paths[j];newPaths[i].clear();search(idx1,curCost,used,newPaths);return;}// Lower bound for jewelry after idxintremainAfter0;for(intjidx1;jk;j){intidorder[j];remainAfterdist[id][sr[id]];}bitsetMAXMpathMask;vectorintpedges;enumPaths(i,idx,curCost,used,paths,pathMask,sr[i],1sr[i],0,pedges,remainAfter);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);while(cinnmk){if(n0m0k0)break;edges.resize(m);adj.assign(n,{});radj.assign(n,{});for(inti0;im;i){inta,b;cinab;--a;--b;edges[i].ua;edges[i].vb;for(intj0;jk;j)cinedges[i].cost[j];adj[a].push_back(i);radj[b].push_back({a,i});}for(inti0;ik;i){cinsr[i]tr[i];--sr[i];--tr[i];}// Dijkstra for each jewelryboolreachabletrue;for(inti0;ik;i){dijkstra(i);if(dist[i][sr[i]]INF)reachablefalse;}if(!reachable){cout-1\n;continue;}// Pre-sort adjacency for each jewelry according to dist to targetfor(inti0;ik;i){for(intu0;un;u){sortedAdj[i][u]adj[u];sort(sortedAdj[i][u].begin(),sortedAdj[i][u].end(),[](inte1,inte2){intv1edges[e1].v,v2edges[e2].v;returndist[i][v1]dist[i][v2];});}}// Determine processing order: by shortest distance descendingorder.resize(k);iota(order.begin(),order.end(),0);sort(order.begin(),order.end(),[](inta,intb){returndist[a][sr[a]]dist[b][sr[b]];});bestCostINF;for(inti0;ik;i)bestPaths[i].clear();// Try greedy initial solutiongetInitialSolution();// Full searchbitsetMAXMemptyUsed;vectorintemptyPaths[MAXK];search(0,0,emptyUsed,emptyPaths);if(bestCostINF){cout-1\n;}else{coutbestCost\n;for(inti0;ik;i){coutbestPaths[i].size();sort(bestPaths[i].begin(),bestPaths[i].end());for(inte:bestPaths[i])cout e1;cout\n;}}}return0;}