P1963 变换序列
题目描述
对于N个整数0，1，…，N-1，一个变换序列T可以将i变成Ti，其中：Ti∈{0，1，…，N-1}且 {Ti}={0，1，…，N-1}。 x，y∈{0，1，…，N-1}，定义x和y之间的距离D(x，y)=min{|x-y|，N-|x-y|}。给定每个i和Ti之间的距离D(i，Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。 说明：对于两个变换序列S和T，如果存在p<N，满足：对于i=0，1，…，p-1，Si=Ti且Sp<Tp，我们称S比T字典序小。
N<=10000
考试时乱水了20分，还不如暴力
之后我一看
发现每一个i最多有2个能与之匹配的T[i]
明显的不带权二分图匹配
可以用匈牙利算法
但是
如果至少存在一个满足要求的变换序列T，则输出一行为N个整数，表示你计算得到的字典序最小的T；
——题目
在匈牙利算法匹配当中，如何才能保证字典序最小呢？
其实就是从后往前寻找匹配，且优先匹配小的T（即连边时小的在前）。
然后就可以兴奋的水过这一题了
其实我考试时把正解写挂了
代码蒯上
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gotcha()
{
register char c = getchar();register long long x = 0, z = 1;
for(;c>'9'||c<'0';c=getchar())z=c=='-'?-1:1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
return x*z;
}
const int _ = 10002;
int n,d[_],to[_]={0},ans[_],e[_][3]={0};
bool ed[_]={0};
int dis(int x,int y){return min(abs(x-y),n-abs(x-y));}
bool finder(int now)
{
for(int i=1;i<=2;i++)
{
if(ed[e[now][i]])continue;
ed[e[now][i]]=1;
if(to[e[now][i]]==-1 || finder(to[e[now][i]]))
{to[e[now][i]]=now;return 1;}
}
return 0;
}
int main()
{
register int i,j,k;
n=gotcha();
for(i=0;i<n;i++)d[i]=gotcha();
for(i=0;i<n;i++)
{
j=(i+d[i])%n,k=(i-d[i]+n)%n;
if(j>k)swap(j,k);
e[i][1]=j;e[i][2]=k;
to[i]=-1;
}
for(i=n-1;i>=0;i--)
{
memset(ed,0,sizeof(ed));
if(!finder(i))
{
printf("%s","No Answer");
return 0;
}
}
for(i=0;i<n;i++)ans[to[i]]=i;
for(i=0;i<n;i++)printf("%d ",ans[i]);
return 0;
}