HDU 3118 Arbiter 判定奇圈

题目来源：

题意：翻译过来就是不能有奇圈 每走一步状态会变化 当他回到起点时假设和原来的状态不一样 可能会死 求至少去掉多少条边能够避免这样的状况发生

思路：二分图是没有奇圈的 最多就15个点 我们用状态压缩枚举那些点是在二分图的一边和另外一边 确定二分图之后枚举输入的边 每条边连接的不能是同一集合的点

不符合就去掉 最后取小

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn = 510;

struct node

{

	int t1, t2, x1, y1, x2, y2;

}a[maxn];

int vis[maxn];

int y[maxn];

vector <int> G[maxn];

int n;

int color[maxn];

int sum = 0;

bool dfs(int u)

{

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

	{

		int v = G[u][i];

		if(vis[v])

			continue;

		vis[v] = true;

		if(y[v] == -1 || dfs(y[v]))

		{

			y[v] = u;

			return true;

		}

	}

	return false;

}

int match()

{

	int ans = 0;

	memset(y, -1, sizeof(y));

	for(int i = 0; i < n; i++)

	{

		memset(vis, 0, sizeof(vis));

		if(dfs(i))

			ans++;

	}

	return ans;

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		int m;

		scanf("%d %d", &n, &m);

		for(int i = 0; i < n; i++)

			G[i].clear();

		while(m--)

		{

			int u, v;

			scanf("%d %d", &u, &v);

			G[u].push_back(v);

			//G[v].push_back(u);

		}

		int ans = 999999999;

		for(int s = 0; s < (1<<n); s++)

		{

			memset(color, 0, sizeof(color));

			for(int i = 0; i < n; i++)

				if(s&(1<<i))

					color[i] = 1;

			sum = 0;

			for(int i = 0; i < n; i++)

				for(int j = 0; j < G[i].size(); j++)

					if(color[i] == color[G[i][j]])

						sum++;

			ans = min(ans, sum);

		}

		printf("%d\n", ans);

	}

	return 0;

}