题目：http://community.topcoder.com/stat?c=problem_statement&pm=13275&rd=16008

由于图中边数不多，选择DFS遍历全部路径，计算路径Inversions时使用了一个R[] 数组，能够在O(N)时间内得到路径Inversions，又由于该图所以路径条数为O(N^2)，算法复杂度为O(N^3)，对于N为1000的限制来说，复杂度较高，但实际測试中，最慢的測试用例费时700多ms，没有超时。若要减小复杂度，须要更高效的算法来计算路径的Inversions，使用 Binary
indexed tree (BIT)数据结构能够达到O(logN), 总复杂的减小到O(N^2logN)。

代码：

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <iostream>

#include <sstream>

#include <iomanip>

#include <bitset>

#include <string>

#include <vector>

#include <stack>

#include <deque>

#include <queue>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <ctime>

#include <climits>

using namespace std;

#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)

typedef pair<int, int> pii;

typedef long long llong;

typedef pair<llong, llong> pll;

#define mkp make_pair

/*************** Program Begin **********************/

const int INF = 1000000000;

class GraphInversions {

public:

	vector <int> V, A, B, adj[1001];

	bool visited[1005];	// 顶点的訪问状态

	int R[1005];		// 用于计算 Inversions, R[weight] 表示当前路径上权值为weight的顶点的个数

	int N, K, ans;

	void DFS(int u, int d, int invs)

	{

		if (d == K) {

			ans = min(ans, invs);

		} else if (d < K) {

			for (int i = 0; i < adj[u].size(); i++) {

				int w = adj[u][i];

				if (visited[w]) {

					continue;

				}

				visited[w] = true;

				++R[ V[w] ];

				DFS(w, d + 1, invs + accumulate(R + V[w] + 1, R + 1001, 0));

				--R[ V[w] ];		// 将顶点从该路径排除

				visited[w] = false;	// 还有一条路径依旧能够使用该顶点

			}

		}

	}

	int getMinimumInversions(vector <int> A, vector <int> B, vector <int> V, int K) {

		int res = INF;

		this->N = A.size();

		this->V = V;

		this->K = K;

		for (int i = 0; i < N; i++) {

			adj[ A[i] ].push_back(B[i]);

			adj[ B[i] ].push_back(A[i]);

		}

		for (int i = 0; i < N; i++) {	// 依次遍历全部顶点，以每一个顶点为起始点进行DFS

			ans = INF;

			memset(visited, 0, sizeof(visited));

			memset(R, 0, sizeof(R));

			visited[i] = true;	// 这一步不要忘，起始点訪问状态应为TRUE

			++R[ V[i] ];		// 将起始点增加到路径中

			DFS(i, 1, 0);

			res = min(res, ans);

		}

		return (res == INF ? -1 : res);

	}

};

/************** Program End ************************/