题意
给出N个阴珠和N个阳珠串成一串，分为阴阳珠，给出m组阴阳珠编号，这些阳珠和阴珠在一块会使得阳珠变暗，求合理的方式使得阳珠暗淡数最小，输出最小值。
思路
首先枚举阴珠相对位置，即固定一个珠的相对位置，利用next_permulation函数讨论其他珠子的相对位置。
next_permutation(yin+2,yin+n+1)，yin数组若为1 2 3 那么yin数组在函数中只会变为 1 2 3、1 3 2，不用有其他变化，因为这里只需要考虑他们的相对位置，其他排列和他们是等价的。
枚举完阴珠之后，会产生N个间隙，然后若阳珠j在间隙i里面不会变暗淡，那么连一条边。求出不会变暗淡的最大值，用n减去，就是会变暗淡的最小值。
#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 200+66 #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define mod 1000000007 #define INF 0x3f3f3f3f struct node { int to; int nxt; } e[maxn*maxn]; struct Two { int head[maxn*2]; int color[maxn]; int dep[maxn]; int dx[maxn]; int dy[maxn]; int mx[maxn]; int my[maxn]; int n,m,cnt; void init(int nn) { cnt=0; n=nn; memset(head,-1,sizeof(head)); } void add_edge(int u,int v) { e[cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt++; } int bfs() { int flag=0; queue<int>q; for(int i=0; i<=n+1; i++) { dx[i]=dy[i]=-1; } for(int i=0; i<n; i++) if(mx[i]==-1) q.push(i); while(!q.empty()) { int u=q.front(); q.pop(); for(int k=head[u]; k!=-1; k=e[k].nxt) { int v=e[k].to; if(dy[v]==-1) { dy[v]=dx[u]+1; if(my[v]==-1) flag=1; else { dx[my[v]]=dy[v]+1; q.push(my[v]); } } } } return flag; } bool dfs(int u) { for(int k=head[u]; k!=-1; k=e[k].nxt) { int v=e[k].to; if(dy[v]==dx[u]+1) { dy[v]=-1; if(my[v]==-1||dfs(my[v])) { my[v]=u; mx[u]=v; return 1; } } } return 0; } int solve() { for(int i=0; i<=n+1; i++) { mx[i]=my[i]=-1; } int ans = 0; while(bfs()) { for(int i = 0; i < n; ++i) if(mx[i] == -1 && dfs(i)) ans++; } return ans; } } D; int a[maxn]; int flag[11][11]; int yin[11]; int main() { int n,m; while(scanf("%d %d",&n,&m)!=EOF) { if(!n) { printf("0\n"); continue; } D.init(n); rep(i,1,n)rep(j,1,n)flag[i][j]=0; rep(i,1,m) { int a,b; scanf("%d %d",&a,&b); flag[a][b]=1; } rep(i,1,n)yin[i]=i; int ans=n; do { //rep(i,1,n)cout<<yin[i]<<" "; //cout<<endl; D.init(n); rep(i,1,n) { rep(j,1,n) { int k=(i==n?1:i+1); if(!flag[j][yin[i]]&&!flag[j][yin[k]]) { D.add_edge(j-1,i-1); } } } ans=min(ans,n-D.solve()); } while(next_permutation(yin+2,yin+n+1)); printf("%d\n",ans); } }
