BZOJ1562 [NOI2009]变换序列 【KM算法】
2024-08-30 01:26:27
题目
输入格式
输出格式
输入样例
5
1 1 2 2 1
输出样例
1 2 4 0 3
提示
30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。
题解
每个位置可以和两种数匹配,显然是一个二分图匹配问题
但要求字典序最小,我们就按字典序存边
由于在KM算法中,后来着具有更高的优先级,我们倒序匹配即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 10005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int lk[maxn],vis[maxn],ans[maxn];
int h[maxn],ne = 1;
struct EDGE{int to,nxt;}ed[maxn << 1];
inline void build(int u,int v){
ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
}
bool find(int u){
Redge(u) if (!vis[to = ed[k].to]){
vis[to] = true;
if (lk[to] == -1 || find(lk[to])){
lk[to] = u;
return true;
}
}
return false;
}
int n,a[maxn],b[maxn];
int main(){
memset(lk,-1,sizeof(lk));
n = read(); int tmp,a,b;
for (int i = 0; i < n; i++){
tmp = read();
a = (i + tmp) % n;
b = (i - tmp + n) % n;
if (a < b) swap(a,b);
build(i,a); build(i,b);
}
for (int i = n - 1; i >= 0; i--){
memset(vis,0,sizeof(vis));
if (!find(i)){
puts("No Answer");
return 0;
}
}
for (int i = 0; i < n; i++) ans[lk[i]] = i;
for (int i = 0; i < n; i++){
printf("%d",ans[i]);
if (i < n - 1) printf(" ");
}
return 0;
}
最新文章
- 如何使iframe透明
- android沉浸式状态栏设置(4.4以上版本)
- MySQL Database on Azure
- 黑马程序员——JAVA基础之反射
- iOS-多线程-内存管理
- 对App数据库元素进行简单的设计
- asp.net 由于代码已经过优化或者本机框架位于调用堆栈之上,无法计算表达式的值
- 玩转Web之JavaScript(一)-----javaScript语法总结(一) 与鼠标操作有关的语法
- Java 中的变量
- [SCOI2005]骑士精神
- 四则运算APP
- Mac 安装 Jenkins
- 20155219 《Java程序设计》实验一(Java开发环境的熟悉)实验报告
- django2.1---后台管理 admin 字段内容过长,省略号替代
- 6款漂亮HTML CSS样式用户留言表单
- chrome浏览器使用
- gif处理
- 升级mojave后的小问题解决
- Xfire实现webservice各种报错详解
- Linux中find
热门文章
- python_66_生成器2
- 漫谈 Clustering (番外篇): Dimensionality Reduction
- CXF学习记录
- react 信用卡格式检验
- vbs自由选择启动bat文件
- Java实现随机出题,10道10以内加减法计算
- [Wolfgang Mauerer] 深入linux 内核架构 第十三章 系统调用
- JavaScript(E5,6) 正则学习总结学习,可看可不看!
- phpstudy iis版本 php4.4.5 和 php5.6.7目录权限问题
- exec , 元类,__new__, __call__ , 单例模式 , 异常