luogu P1963 [NOI2009] 变换序列
题意
对于\(N\)个整数\(0, 1, \cdots, N-1\)，一个变换序列\(T\)可以将\(i\)变成\(T_i\)，其中 \(T_i \in \{ 0,1,\cdots, N-1\}\) 且 \(\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}\)。 ，\(\forall x,y \in \{0,1,\cdots , N-1\}\)，定义x和y之间的距离\(D(x,y)=min\{|x-y|,N-|x-y|\}\) 。给定每个\(i\)和\(T_i\)之间的距离\(D(i,T_i)\)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。
说明：对于两个变换序列\(S\)和\(T\)，如果存在\(p<N\)，满足对于\(i=0,1,\cdots p-1\)，\(S_i=T_i\)且\(S_p<T_p\)，我们称\(S\)比\(T\)字典序小。
题解
难受啊。但感觉这题还是不错的。
我们知道了 \(D(i,T_i)\) 其实就已经很有启发感了，这并不是一个很难的方程。
解完方程之后我们会发现每一个 \(T_i\) 都有大概四种可能。
题目要求的是每一个数都只能使用一次，这里其实暗示的已经很明显了。
我们将 \(i\) 作为左部，\(T_i\) 作为右部，每一对其实就是一对匹配，有解就是有完美匹配。
有解的问题解决了，剩下的就是字典序。
我们想一下最大匹配的过程，由于是按顺序找增广路的，撤销只会撤销前面已经匹配的点。
所以有一个显然的想法，将左部的连边从小到大排序，然后再倒序匹配，这样乍一看好像是对的。
因为前面的优先级大于后面的，为了让前面的尽量小我们只会牺牲后面的，而后面的再大也没什么关系。
这个结论在这个题中是对的，在一般二分图中就不对了。 这里放一个偷的图。
错在哪里呢?这个策略的贪心只是保证了当前位最优，而后面的撤销不能保证是最优的。
我们不妨将思路换一换，在一些字典序最小的题中有一个经典的操作，在保证有解的情况下按位依次尽量小。
这题中我们就可以这样操作。
还是将所有出边从小到大排序，按顺序依次寻找增广路，将当前这条边对应的两点删掉，跑一边最大匹配，若依然有解则不添回来，否则添回来然后继续寻找增广路，这样做的时间复杂度是 \(O(m^2n)\) 的。
但实际上还有优化的空间，我们每次只用判断有无解，而删除一条边并不会影响全局，只会影响两端的和其有关的边。
所以我们可以一开始就跑一遍最大匹配，然后和上面一样填数，如果要修改一条边，我们只需要考虑修改到这里的边原来对应的左部的点能不能找到一条增广路就行了，这足以判断有没有最大匹配。 然后和上面一样判断删不删就行了，时间复杂度 \(O(n^2m)\) ，
code
#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
const int N = 2e4+5 ;
int n,ans ;
int d[N],T[N],linkx[N],linky[N],ed[N],vis[N] ;
vector<int>e[N] ;
bool S_GND ;
int Dfs(int x)
{
if(vis[x] || ed[x]) return 0 ; vis[x] = 1 ;
for(auto v:e[x]) if(!ed[v+n] && (!linky[v] || Dfs(linky[v])))
{
linkx[x] = v,linky[v] = x ; return 1 ;
} return 0 ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n) ;
FOR(i,1,n,1) read(d[i]) ;
FOR(i,1,n,1)
{
if(i+d[i] <= n) e[i].pb(i+d[i]) ;
if(i-d[i] >= 1) e[i].pb(i-d[i]) ;
if(n+i-d[i] <= n) e[i].pb(n+i-d[i]) ;
if(i+d[i]-n >= 1) e[i].pb(i+d[i]-n) ;
sort(e[i].begin(),e[i].end()) ;
if(d[i] > n/2) {puts("No Answer") ; return 0 ;}
}
FOR(i,1,n,1) me(vis,0),ans += Dfs(i) ;
if(ans < n) {puts("No Answer") ; return 0 ;}
FOR(i,1,n,1) for(auto v:e[i])
{
int rp = 0 ;
if(linkx[i] == v) rp = 1 ;
else
{
ed[i] = ed[v+n] = 1,linky[linkx[i]] = 0,me(vis,0) ;
if(Dfs(linky[v])) rp = 1 ;
else linky[linkx[i]] = i ; ed[i] = ed[v+n] = 0 ;
}
if(rp) {ed[i] = ed[v+n] = 1 ; print(v-1) ; break ;}
}
return 0 ;
}
...
总结一下这题有些什么trick。
1.关于字典序的题目可能可以在保证满足条件的情况下填位。
2.最大匹配修改边看有无解只需要判断修改的点能不能搜出增广路，这样类似的思想应该也能推广到其它题中。