题目链接:
题目大意:
给出一个序列(0~n-1),这个序列经过某个变换会成为另外一个序列,但是其中的元素不会改变,给出初始序列与变换后的序列每一位上的“距离”,求字典序最小的变换序列。#cp
题解:
匈牙利求二分图的最大匹配
//居然A了QwQ好感人 就是把一个元素跟它能变幻到的连边,(为什么我感觉可以有四种orz然后大家说的是最多两条边可能是我没有仔细研究=-=)。然后跑匈牙利看看能否完美匹配就好了。 由于方案要字典序最小,所以考虑选边的顺序。让比较小的先被选到,就是大的先连。而匈牙利中从N-1开始匹配。因为越早匹配完成,后面的点如果与前面的产生冲突,那么一定是先完成匹配的点(编号更大的)的匹配点变大。
#include#include #include #include #include using namespace std;#define maxn 10100struct node{ int x,y,next;}a[maxn*4];int len,first[maxn];int d[maxn],as[maxn],bf[maxn],ask[maxn],tim;void ins(int x,int y){ len++;a[len].x=x;a[len].y=y; a[len].next=first[x];first[x]=len;}bool ffind(int x){ for (int i=first[x];i!=-1;i=a[i].next) if (ask[a[i].y]!=tim) { int y=a[i].y; ask[y]=tim; if (bf[y]==-1 || ffind(bf[y])) { bf[y]=x;as[x]=y; return true; } } return false;}int main(){ int n,i,ans; scanf("%d",&n); len=0;memset(first,-1,sizeof(first)); for (i=0;i n-d[i]) { if (i+d[i] =n-d[i]) ins(i,i-n+d[i]); if (i>=d[i]) ins(i,i-d[i]); }else { if (i+n-d[i] =d[i]) ins(i,i-d[i]); if (i>=n-d[i]) ins(i,i-n+d[i]); } } ans=tim=0; memset(bf,-1,sizeof(bf)); memset(ask,0,sizeof(ask)); for (i=n-1;i>=0;i--) { tim++; if (ffind(i)) ans++; } if (ans!=n) printf("No Answer\n"); else { printf("%d",as[0]); for (i=1;i