poj 1422题目链接 题意+思路：DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。 /* *********************************************** Author :111qqz Created Time :2016年05月26日 星期四 20时24分15秒 File Name :code/poj/r2594.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> …

poj 2594 题目链接 题意：一个DAG图，每个点有宝藏...可以降落任意个机器人到任意点...然后机器人可以沿着路径走，路过某个点的时候，可以取走该点的宝藏。问要取走所有宝藏，最少需要多少个机器人。 思路：乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候，可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point. ” 那是否还可以用最小路径覆盖做呢。。答案是可以的。。。 区别就在于一个点如果被一条路径使用过一次，还可不 …