hdu 5727 二分图+环排列

Necklace

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2423 Accepted Submission(s): 766

Problem Description

SJX has 2*N magic gems.

Input

Multiple test cases.

For each test case, the first line contains two integers

Output

One line per case, an integer indicates that how many gem will become somber at least.

Sample Input

2 1 1 1 3 4 1 1 1 2 1 3 2 1

Sample Output

1 1

/*
hdu 5727 二分图+环排列

problem:
要用ｎ个阳石和ｎ个阴石来串一个项链（环状），规定阳石旁边只能是阴石，阴石旁只能是阳石，现在有ｍ对特殊阴阳石，
这些阴阳石相邻会使得阳石出故障（照样可以用），问串这个项链，至少有几个故障的阳石。

solve:
最开始一看题就感觉应该是二分匹配,发现往环的阴石中添加阳石每个位置要考虑左右两边的情况
所以可以枚举阴石的所有情况.然后对每个空位和所有阳石之间建图。即这里可以放阳石就置为1,然后跑个最大匹配得出cnt
那么n-cnt就是当前情况最少的故障数

枚举这个是用的系统自带的next_permutation,但是一直超时.后来看别人题解才发现环排列只需要(n-1)!.所以可以固定一个
位置的值,枚举剩下的即可

hhh-2016-08-16 11:07:51
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
#define lson  i<<1
#define rson  i<<1|1
#define ll long long
#define key_val ch[ch[root][1]][0]
using namespace std;
const int maxn = 11;
const int inf = 10000;
struct node
{
    int to,next;
} edge[maxn*maxn];
int tot;
int tmap[maxn][maxn];
int head[maxn];

void add(int u,int v)
{
    edge[tot].to = v,edge[tot].next = head[u];
    head[u] = tot++;
}
int link[maxn],vis[maxn];
bool dfs (int u)
{
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if (!vis[v])
        {
            vis[v] = 1;
            if (link[v] == -1 || dfs (link[v]))
            {
                link[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int n,m;
int ans = inf;

int cal()
{
    int res = 0;
    memset(link,-1,sizeof(link));
    for(int i = 1; i <= n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            res ++;
    }
    return n-res;
}
int po[maxn*2];

int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {

        memset(tmap,0,sizeof(tmap));
        int a,b;
        for(int i =1; i <= m; i++)
        {
            scanf("%d%d",&a,&b);
            tmap[a][b] = 1;
        }
        if(!n || !m)
        {
            printf("0
");
            continue;
        }
        for(int i = 1; i <= n; i++)po[i] = i;
        ans = inf;
        do
        {
            tot = 0;
            memset(head,-1,sizeof(head));
            for(int i =1; i <= n; i++)
            {
                for(int j = 1; j <= n; j++)
                {
                    int pre = i-1,next = i;
                    if(!pre) pre = n;
                    if(!tmap[j][po[pre]] && !tmap[j][po[next]])
                        add(j,i);
                }
            }
            ans = min(ans,cal());
            if(!ans)
                break;
        }
        while(next_permutation(po+2,po+n+1));
        printf("%d
",ans);
    }
    return 0;
}