Link: Arbiter

Arbiter

Arbiter is a kind of starship in the StarCraft science-fiction series. The Arbiter-class starship is a Protoss warship specializing in providing psychic support. Arbiters were crewed exclusively by Judicators; unlike other warships that were manned predominantly by Templar. The Judicator used the Arbiter as a base to provide support using space-time manipulation.
Arbiters could weaken space-time, tearing rifts in the fabric of space-time, creating a vortex linking another location to the Arbiter’s location. This could be used to move personnel over long distances between stars.
In the meantime of widely used Arbiter to transfer, KMXS, the captain of one Arbiter, was warning that some person had got a serious mental disorder after the trip on his Arbiter. By using mice as model animals, he found the sake, it’s because of chirality!
Every person has chirality, either left-handed or right-handed. Actually all the persons must live with the food which has the same chirality. When one person took Arbiter from one star to another one, his chirality will be changed (from left-handed to right-handed or from right-handed to left-handed). If a person took a long trip and finally got back to his own star, however, his chirality might be changed to the opposite state other than his original, which would cause fatal mental disorder, or even death.
KMXS has the channels map among the starts and he need to prohibit minimum number of channels from traveling so that wherever a person starts his traveling from when he gets his original star he’ll be safe. KMXS turns to your help.

Input
The first line of input consists of an integer T, indicating the number of test cases.
The first line of each case consists of two integers N and M, indicating the number of stars and the number of channels. Each of the next M lines indicates one channel (u, v) which means there is a bidirectional channel between star u and star v (u is not equal to v).

Output
Output one integer on a single line for each case, indicating the minimum number of channels KMXS must prohibit to avoid mental disorder.

Constraints
0 < T <= 10
0 <= N <= 15 0 <= M <= 300
0 <= u, v < N and there may be more than one channel between two stars.
Sample Input
1
3 3
0 1
1 2
2 0

Sample Output
1

Problem solving:
这道题的题意我没看。但是让你求的就是给你一个平凡图，问你最少需要删几条边使得图中没有奇环（即一个环是由奇数个边连起来的）。
上海站的那道题跟这个简直一模一样，枯了。

二分图，一个图是二分图的充要条件是图中所有的环都是偶环，全都是偶环也就是没有奇环。并且这个题目数据范围也不大，最多还不到16个点，所以我们可以使用二进制枚举来写。二进制位是0的是二分图的一边，是1的就是二分图的另一边，如果出现在同一边的两个点之间有一条边，删除即可。枚举每一种情况，16个点，2^16种情况，每次更新最小值即可。

Code:

#include <iostream>
using namespace std;
const int maxn = 521;
struct node
{
    int u, v;
} a[maxn];
int main()
{
    int t, n, m;
    cin >> t;
    while (t--)
    {
        int ans = 0x3f3f3f3f;
        cin >> n >> m;
        for (int i = 0; i < m; i++)
            cin >> a[i].u >> a[i].v;
        for (int i = 0; i < (1 << n); i++)
        {
            int mid = 0;
            for (int j = 0, u, v; j < m; j++)
            {
                u = a[j].u, v = a[j].v;
                if (((i >> u) & 1) == ((i >> v) & 1))
                    mid++;
            }
            ans = min(ans, mid);
        }
        cout << ans << endl;
    }
    return 0;
}

反思一下：二分图和二进制枚举也不是没学过，不会使用，真的是自己的锅，以后加油！

赏