hdu5727

题意:
给你最n个阳珠子和n个阴珠子（n≤9），要你串成阴阳相隔的珠链,有一些阳珠子不能和某些阴珠子放一起,否则会失去光芒,询问至少有几个阳珠子失去光芒.

因为阴阳相隔，所以我们可以考虑枚举阴珠子的全排列，在阴珠子之间插入阳珠子完成，插入使用二分图匹配完成。
优化:
1.考虑旋转，锁定全排列中第一个数字即可
2.考虑翻转，hash环排列以及他的翻转排列即可

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-12;
struct dinic{
    static const int maxn=30;
    static const int maxm=900;
    static const int inf=1e9;
    struct edge{
        int v,nex;
        double c;
    } g[2*maxm];
    int lv[maxn],current[maxn],head[maxn],cnt;
    
    void add_edge(int u,int v,double c){
       //cout<<u<<" "<<v<<endl;
        g[cnt].v=v;
        g[cnt].c=c;
        g[cnt].nex=head[u];
        head[u]=cnt++;
        
        g[cnt].v=u;
        g[cnt].c=0;
        g[cnt].nex=head[v];
        head[v]=cnt++;
    }
    
    void ini(){
        memset(head,-1,sizeof(head));
        cnt=0;
    }
    
    void bfs(int s){
        memset(lv,-1,sizeof(lv));
        lv[s]=0;
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=head[u]; ~i; i=g[i].nex){
                edge&e=g[i];
                //if(e.c<=0||lv[e.v]>=0)continue;
                if(e.c<2*eps||lv[e.v]>=0)continue;
                lv[e.v]=lv[u]+1;
                q.push(e.v);
            }
        }
    }
    
    double dfs(int u,int t,double f){
        if(u==t)return f;
        for(int&i=current[u]; ~i; i=g[i].nex){
            edge&e=g[i],&rev=g[i^1];
            //if(e.c<=0||lv[u]>=lv[e.v])continue;
            if(e.c<eps||lv[u]>=lv[e.v])continue;
            double d=dfs(e.v,t,min(f,e.c));
            //if(d<=0)continue;
            if(d<eps)continue;
            e.c -=d;
            rev.c+=d;
            return d;
        }
        return 0;
    }
    
    double maxflow(int s,int t){
        double flow=0;
        while(true){
            memmove(current,head,sizeof(head));
            bfs(s);
            if(lv[t]<0)return flow;
            double f;
            //while((f=dfs(s,t,inf))>0)flow+=f;
            while((f=dfs(s,t,inf))>eps)flow+=f;//注意括号
        }
    }
} g;


bool limit[20][20];
int a[20];

int gethash(int*a,int n){// [1,n]
    int ret=a[1];
    for(int i=2;i<=n;i++){
        ret*=10;
        ret+=a[i];
    }
    return ret;
}
int gethashrev(int*a,int n){// [1,n]
    int ret=a[1];
    for(int i=n;i>=2;i--){
        ret*=10;
        ret+=a[i];
    }
    return ret;
}

map<int,bool>mp;

int solve(int *a,int n){
    g.ini();
    int s=2*n+1;
    int t=2*n+2;
    
    for(int i=1;i<=n;i++){
        g.add_edge(s, i, 1);
        g.add_edge(i+n,t,1);
        
        for(int j=1;j<=n;j++){
            if((!limit[a[i]][j])&&(!limit[a[i+1]][j])){
                g.add_edge(i, j+n, 1);
            }
        }
    }
    
    return g.maxflow(s,t)+0.5;
}



int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(n==0){
            cout<<0<<endl;
            continue;
        }
        //init
        for(int i=1;i<=n;i++)a[i]=i;
        a[n+1]=1; //a[i]..a[i+1]   1<=i<=n
        memset(limit,0,sizeof(limit));
        mp.clear();
        
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            limit[v][u]=true;
        }
        
        int ans=1000;
        
        do{
            int hash=gethash(a,n);
            if(mp[hash]==true)continue;
            mp[hash]=true;
            mp[gethashrev(a,n)]=true;
            ans=min(ans,n-solve(a,n));
            
        }while(next_permutation(a+2,a+1+n));
        
        cout<<ans<<endl;
    }
}