BZOJ1562——[NOI2009]变换序列
2024-10-03 16:26:11
1、题意:题意有些难理解
2、分析:我们发现如果要求判断是否合法的话就so easy了,二分图匹配即可,但是我们发现要求输出字典序最小的,那么我们在匈牙利的时候就倒着枚举,另外邻接表中的边一定要排好序,如果用的是链表的话,就从大到小,vector就从小到大插入,然后我们就可以保证字典序最小了,想了半天网络流QAQ,看了题解。。匈牙利是啥都快忘记了。。。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 20010
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct Edge{
int u, v, next;
} G[M];
int head[M], tot;
int tim;
int pre[M], vis[M];
inline void add(int u, int v){
G[++ tot] = (Edge){u, v, head[u]};
head[u] = tot;
}
inline bool dfs(int u){
for(int i = head[u]; i != -1; i = G[i].next){
if(vis[G[i].v] != tim){
vis[G[i].v] = tim;
if(pre[G[i].v] == -1 || dfs(pre[G[i].v])){
pre[G[i].v] = u;
pre[u] = G[i].v;
return 1;
}
}
}
return 0;
}
int main(){
memset(head, -1, sizeof(head));
memset(pre, -1, sizeof(pre));
int n = read();
for(int i = 1; i <= n; i ++){
int d = read();
int a = i - d, b = i + d;
if(a <= 0) a += n;
if(b > n) b -= n;
a += n; b += n;
if(a < b) swap(a, b);
add(i, a); add(i, b);
}
for(int i = n; i >= 1; i --){
tim ++;
if(!dfs(i)){
printf("No Answer");
return 0;
}
}
for(int i = 1; i < n; i ++) printf("%d ", pre[i] - n - 1);
printf("%d\n", pre[n] - n - 1);
return 0;
}
最新文章
- 5Hibernate配置及使用方法----青软S2SH(笔记)
- 【iCore3 双核心板】例程十三:SDIO实验——读取SD卡信息
- 动画---图形图像与动画(三)Animation效果的XML实现
- HTML相对路径 当前目录、上级目录、根目录、下级目录表示法
- Format可能存在的坑
- 去掉IntelliJ IDEA的拼写检查
- tomcat启动报错:Unsupported major.minor version 51.0
- Java学习----不变的常量
- 属性动画 LayoutTransition AnimatorInflater Keyframe 新特性
- Spring之SpringMVC的RequestToViewNameTranslator(源码)分析
- Oozie时出现Exception in thread ";main"; java.lang.UnsupportedClassVersionError: com/mysql/jdbc/Driver : Unsupported major.minor version 52.0?
- Oracle 10g 应用补丁PSU 10.2.0.5.180717
- HTTP &;RFC
- git 和github使用
- PHP之魔术方法
- C++拷贝构造函数的调用时机
- python使用SAX解析xml
- ArcGIS案例学习笔记2_2_模型构建器和山顶点提取批处理
- mfc Edit控件属性
- 撩课-Web大前端每天5道面试题-Day8