500:最多50个点的一棵树，每条边代表一盏灯，有两种状态，开或关，还有两种属性，重要或者不重要
定义一种操作是选择一条路径，将路径上的边的开关状态取反。问最少需要多少次操作才能使得每条重要的边都处于开的状态。
显然，所有的不重要的边都可以合并起来，然后搞成一棵新的树，每条边都是重要的，然后再YY一下，每条已经开的边不需要被覆盖到了，因为取反后还是要取反回来的，这样跟不去取反是一样的，所以现在这棵树被拆分成了若干棵树，每棵树全是需要取反的边，根据奇偶性贪心取即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;class TurnOnLamps{public: int minimize(vector roads, string initState, string isImportant); // BEGIN CUT HEREpublic:void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }private:template string print_array(const vector os <<"{ "; for (typename vector::const_iterator iter = V.begin(); iter != V.end(); ++iter) os <<‘\"‘ <<*iter <<"\","; os <<" }"; return os.str(); }void verify_case(int Case, const int if (Expected == Received) cerr <<"PASSED" < 【文章转自高防服务器 http://www.558idc.com 复制请保留原URL】