【洛谷P1963】变换序列

题目大意：对于一个顺序序列，求一个合法置换，可以满足一些约束，若存在多个合法置换，则输出字典序最小的一个置换。

题解：对于序列的置换是否有解的问题，可以和二分图的完美匹配相关联。由于是字典序最小，显然需要贪心考虑。在匈牙利算法执行的过程中，对于每个点来说，可以优先匹配符合条件的最小的点；对于左边点集来说，可以从后往前进行匹配，这样可以保证字典序小的点更可能抢到字典序小的点。

代码如下

#include <bits/stdc++.h>

#define pb push_back

#define all(x) x.begin(),x.end()

using namespace std;

const int maxn=1e4+10;

vector<int> G[maxn];

int n,match[maxn],t[maxn];

bool vis[maxn];

void read_and_parse(){

	scanf("%d",&n);

	for(int i=0;i<n;i++){

		int d;scanf("%d",&d);

		int x=(i-d+n)%n,y=(i+d)%n;

		G[i].pb(x),G[i].pb(y);

	}

	for(int i=0;i<n;i++)sort(all(G[i]));

}

bool dfs(int u){

	for(auto v:G[u])if(!vis[v]){

		vis[v]=1;

		if(!match[v]||dfs(match[v])){

			match[v]=u;return 1;

		}

	}

	return 0;

}

void solve(){

	int ret=0;

	for(int i=n-1;i>=0;i--){

		memset(vis,0,sizeof(vis));

		if(dfs(i))++ret;

	}

	if(ret<n)return (void)puts("No Answer");

	for(int i=0;i<n;i++)t[match[i]]=i;

	for(int i=0;i<n;i++)printf("%d ",t[i]);

	puts("");

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P1963】变换序列

最新文章

热门文章