Gym - 101503I 利用到图论的构造
2024-08-29 10:49:50
比赛的时候没有注意到 给出的up矩阵 能使我们随便选一列 确定这一列的rank
这样我们得出每一行列的rank 进行构图 大->小 然后从大到小放 当前放的点 和他有因果关系并且比他大的点必须已经被放了 并且这个图没有环
做一个topsort就可以了
但是会MLE 因为边的数量可能 600^3 这个图虽然满足拓扑图 但是它比拓扑图更满足一个严格的等级序列
所以可以只建600^2的边 每个点指向只比它小的点
需要判断输入的合法性
int n ;
int le[605][605] ;
int up[605][605] ;
int d[605][605] ;
int deg[605*605] ;
int ans[605][605] ; int head[605 * 605] ;
struct edge{
int v,nex;
}b[605 * 605 * 2] ;
int tot ;
void add(int u,int v){
tot ++ ;
b[tot].v=v ; b[tot].nex=head[u];
head[u]=tot ;
} bool topso() {
int cnt = n*n ;
queue<int>que ;
while(!que.empty()) que.pop() ;
rep(i,1,n*n) {
if(deg[i] == 0) {
que.push(i) ;
}
}
while(!que.empty()) {
int u = que.front() ; que.pop() ;
int x = (u+n-1)/n;
int y = (u%n) ; if(y==0)y=n;
ans[x][y] = cnt -- ;
rnode(i,u){
int v=b[i].v;
deg[v]--;
if(deg[v]==0){
que.push(v) ;
}
}
}
return cnt == 0 ;
} int main () {
tot = 0 ;
flc(head,-1) ;
n = read() ;
rep(i,1,n) rep(j,1,n) up[i][j] = read() ;
rep(i,1,n) rep(j,1,n) le[i][j] = read() ;
rep(i,1,n) rep(j,1,n) {
if(up[i][j] >= i || le[i][j] >= j) {
printf("0\n") ; return 0 ;
}
}
rep(i,1,n) rep(j,1,n) d[i][j] = (i-1)*n + j ;
flc(deg,0) ;
rep(i,1,n) {
int a[650] ;
a[1] = d[i][1] ;
rep(j,2,n) {
int m = le[i][j] ;
m ++ ;
dow(k,j,m+1) a[k] = a[k-1] ;
a[m] = d[i][j] ;
}
rep(j,1,n-1) {
add(a[j],a[j+1]) ;
deg[a[j+1]] ++ ;
}
}
rep(j,1,n) {
int a[650] ;
a[1] = d[1][j] ;
rep(i,2,n) {
int m = up[i][j] ;
m ++ ;
dow(k,i,m+1) a[k] = a[k-1] ;
a[m] = d[i][j] ;
}
rep(i,1,n-1) {
add(a[i],a[i+1]) ;
deg[a[i+1]] ++ ;
}
}
if(topso()) {
rep(i,1,n) rep(j,1,n) {
printf("%d" , ans[i][j]) ; fmt(j,n) ;
}
}
else {
printf("0\n") ;
}
}
最新文章
- Codeigniter基础
- 在访问jsp时抛java.lang.IllegalArgumentException: Page directive: invalid value for import的原因
- Stencil Buffer
- JQuery 操作按钮遮罩(删除)
- PowerShell监控Windows打印服务器
- nodejs简单层级结构配置文件
- CGI与Servlet的区别和联系
- MySql拾遗
- Delphi判断文件是否正在被使用(CreateFile也可以只是为了读取数据,而不是创建)
- ajax动态加入的元素不被jquerymobile渲染问题
- WEB 端批量移动设备管理控制工具 STF 的环境搭建和运行
- Codeforces Round #467 (Div. 1) B. Sleepy Game
- 网络-udp
- WebPack命令执行的时候,其内部处理逻辑是什么
- Django 安装配置
- Redis5种常用的数据结构
- Confluence 6 设置 Oracle 数据库准备
- Alpha冲刺 - (4/10)
- linux的可中断sleep_on函数分析
- Luogu 4556 雨天的尾巴 - 启发式合并线段树
热门文章
- 邮件发送模型及其Python应用实例
- 【BZOJ4439】[Swerc2015]Landscaping 最小割
- java反射——构造方法
- window下使用mysql,报未定义标识符";SOCKET";
- 转!!Tomcat网站上的core和deployer的区别
- c++编译/连接/运行
- 深入理解CNI
- Android Studio "佛祖保佑 永无bug" 注释模板设置详解(仅供娱乐)
- 我的Android进阶之旅------>解决:debug-stripped.ap_' specified for property 'resourceFile' does not exist.
- Andrew Ng机器学习编程作业:Neural Network Learning