srm 583

500:最多50个点的一棵树，每条边代表一盏灯，有两种状态，开或关，还有两种属性，重要或者不重要

定义一种操作是选择一条路径，将路径上的边的开关状态取反。问最少需要多少次操作才能使得每条重要的边都处于开的状态。

显然，所有的不重要的边都可以合并起来，然后搞成一棵新的树，每条边都是重要的，然后再YY一下，每条已经开的边不需要被覆盖到了，因为取反后还是要取反回来的，这样跟不去取反是一样的，所以现在这棵树被拆分成了若干棵树，每棵树全是需要取反的边，根据奇偶性贪心取即可。

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;

class TurnOnLamps
{
public: 
    int minimize(vector <int> roads, string initState, string isImportant);
    
    
// BEGIN CUT HERE
	public:
	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 <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << ‘\"‘ << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << ‘\"‘ << endl; cerr << "\tReceived: \"" << Received << ‘\"‘ << endl; } }
	void test_case_0() { int Arr0[] = {0, 0, 2, 3, 4, 5, 6, 4, 8, 4, 5, 11, 11, 13, 11, 12, 14, 15, 16, 17, 20, 18, 20, 22, 21, 22, 22, 27, 24, 26, 29, 30, 29, 29, 34, 35, 33, 33, 36, 38, 37, 41, 42, 42, 43, 42, 42, 47, 46}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "0101010010110001010011000011111100100110110110101"; string Arg2 = "1111111101111111111110111111111011111110110111111"; int Arg3 = 13; verify_case(0, Arg3, minimize(Arg0, Arg1, Arg2)); }
	void test_case_1() { int Arr0[] = {0,0,1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "0000"; string Arg2 = "0111"; int Arg3 = 2; verify_case(1, Arg3, minimize(Arg0, Arg1, Arg2)); }
	void test_case_2() { int Arr0[] = {0,0,1,1,4,4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "000100"; string Arg2 = "111111"; int Arg3 = 2; verify_case(2, Arg3, minimize(Arg0, Arg1, Arg2)); }
	void test_case_3() { int Arr0[] = {0,0,1,1,4,4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "100100"; string Arg2 = "011101"; int Arg3 = 2; verify_case(3, Arg3, minimize(Arg0, Arg1, Arg2)); }
	void test_case_4() { int Arr0[] = {0,0,2,2,3,1,6,3,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "010001110"; string Arg2 = "000110100"; int Arg3 = 1; verify_case(4, Arg3, minimize(Arg0, Arg1, Arg2)); }
	void test_case_5() { int Arr0[] = {0,0,1,2,4,4,6,1,2,5,2,8,8,3,6,4,14,7,18,14,11,7,1,12,7,5,18,23,0,14,11,10,2,2,6,1,30,11,9,12,5,35,25,11,23,17,14,45,15}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "0000000000010000000000000010000010100000000000000"; string Arg2 = "1010111111111011011111000110111111111111111110111"; int Arg3 = 14; verify_case(5, Arg3, minimize(Arg0, Arg1, Arg2)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
    TurnOnLamps ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE
int fa[55];
int g[55][55];
int find(int x) {
  return fa[x] == x ? x : find(fa[x]);
}
void Union(int x,int y) {
  int fx = find(x);
  int fy = find(y);
  if(fx != fy) {
    fa[fx] = fy;
  }
}
bool vis[55];
int n;
int owe[55];
int ans;
void dfs(int u,int f,int state) {
  vis[u] = true;
  int cnt = 0, sum = 0;
  for(int i = 1; i < n; i++) {
    if(g[u][i] != -1 && !vis[i]) {
      dfs(i, u, g[u][i]);
      cnt ^= g[u][i];
      sum += g[u][i];
      if(g[u][i] == 0) {
        ans += owe[i];
      }
    }
  }
  owe[u] = cnt;
  ans += sum / 2;
}
int TurnOnLamps::minimize(vector <int> roads, string initState, string isImportant){
  ans = 0;
  memset(owe, 0, sizeof(owe));
  for(int i = 0; i < 50; i++) fa[i] = i;
  memset(g, -1, sizeof(g));
  n = roads.size() + 1;
  for(int i = 0; i < roads.size(); i++) {
    int a = roads[i];
    int b = i + 1;
    if(isImportant[i] == ‘0‘) {
      Union(a, b);
    } 
  }
  for(int i = 0; i < roads.size(); i++) {
    int a = roads[i];
    int b = i + 1;
    int x = find(a);
    int y = find(b);
    if(x != y)  g[x][y] = g[y][x] = (initState[i] == ‘0‘ );
  }
  int root = find(0);
  memset(vis, false, sizeof(vis));

srm 583

原文：http://blog.csdn.net/crazy_ac/article/details/18972211