生活随笔
收集整理的这篇文章主要介绍了
BZOJ 1562 变换序列
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
二分图匹配
要求字典序最小
匈牙利算法
自N-1至0尝试匹配
先尝试小数，这个通过加边顺序控制
这样高优先权位置只有在不可行时才取大数
#include <iostream>using namespace std;const int MAXN=11111;int N;
int D[MAXN];
int F[MAXN], IF[MAXN];int Norm(int k){if(k>=N) k-=N;if(k<0) k+=N;return k;
}struct Vert{int FE;int Dfn;
} V[MAXN];struct Edge{int x, y, next;
} E[MAXN<<1];int Ecnt=0;void addE(int a, int b){++Ecnt;E[Ecnt].x=a;E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;
}int DFN=0;bool DFS(int at){if(V[at].Dfn==DFN) return false;V[at].Dfn=DFN;for(int k=V[at].FE, to;k>0;k=E[k].next){to=E[k].y;if(IF[to]<0 || DFS(IF[to])){F[at]=to;IF[to]=at;return true;}}return false;
}void show(){cout << endl;for(int i=0;i<N;++i) cout << F[i] << " ";cout << endl;for(int i=0;i<N;++i) cout << IF[i] << " ";cout << endl;cout << endl;
}int Cnt=0;int main(){ios_base::sync_with_stdio(false);cin >> N;for(int i=0;i<N;++i) cin >> D[i];for(int i=0, x, y;i<N;++i){x=Norm(i+D[i]);y=Norm(i-D[i]);if(x>y) swap(x, y);addE(i, y);if(x!=y) addE(i, x);}for(int i=0;i<N;++i){F[i]=-1;IF[i]=-1;}//for(int i=0;i<N;++i)for(int i=N-1;i>=0;--i){if(F[i]<0){++DFN;if(DFS(i))++Cnt;}//show();}//cout << Cnt << endl;if(Cnt==N){for(int i=0;i<N;++i)cout << F[i] << " ";cout << endl;}else cout << "No Answer" << endl;return 0;
}/*
5
1 1 2 2 11 2 4 0 3*/
转载于:https://www.cnblogs.com/Pickupwin/p/9155776.html
总结
以上是生活随笔为你收集整理的BZOJ 1562 变换序列的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
