首页 > ACM题库 > HDU-杭电 > HDU 3118-Arbiter-分治-[解题报告]HOJ
2014
03-02

HDU 3118-Arbiter-分治-[解题报告]HOJ

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.

输入:

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).

输出:

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).

样例输入:

1
3 3
0 1
1 2
2 0

样例输出:

1

#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 300 + 5;
const int INF = 100000 + 5;

int from[maxn],to[maxn];
int col[20];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 0;i < m;i++) scanf("%d%d",&from[i],&to[i]);
        int ans = m;
        for(int i = 0;i < (1 << n);i++){
            int tem = i;
            for(int j = 0;j < n;j++){
                col[j] = tem%2;
                tem /= 2;
            }
            int sum = 0;
            for(int j = 0;j < m;j++){
                int x = from[j];
                int y = to[j];
                if(col[x] == col[y]) sum++;
            }
            ans = min(ans,sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/wiking__acm/article/details/12219759


  1. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  2. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  3. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  4. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  5. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  6. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  7. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  8. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  9. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  10. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏

  11. 给力的无敌小游戏网站17yy,广告可以跳过的网站,游戏更新,无敌版最快的网站,一起玩玩,17yy。啥也不说了,就是不给qb啥的也要顶,真的是个良心网站。 最喜欢金庸系列,盗版三国志系列~~~~!!!! ~!@17yy小游戏