P1653 [USACO04DEC] Cow Ski Area G

315 字
2 分钟
P1653 [USACO04DEC] Cow Ski Area G

题解#

一句话:输出缩点后的出度为 00 的点的个数和入度为 00 的点的个数的最大值

首先对这个矩阵进行建模,如果能滑到就建一条单向边。

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i>1&&a[i-1][j]<=a[i][j]){
adding(cal(i,j),cal(i-1,j));
}
if(i<n&&a[i+1][j]<=a[i][j]){
adding(cal(i,j),cal(i+1,j));
}
if(j>1&&a[i][j-1]<=a[i][j]){
adding(cal(i,j),cal(i,j-1));
}
if(j<m&&a[i][j+1]<=a[i][j]){
adding(cal(i,j),cal(i,j+1));
}
}
}

然后使用 Tarjan 进行缩点,最后记录缩点后的入度和出度就可以了,答案就是出度为 00 的强连通分量的个数和入度为 00 的强连通分量的个数取 max⁡\max,最后不要忘了特判一下如果只有一个强连通分量的话就不需要建立任何一道缆车。

code#

#include<bits/stdc++.h>
using namespace std;
const int N=250005;
int n,m,head[N],cnt,a[505][505];
struct Edge{
int to;
int next;
}e[4*N];
void adding(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int cal(int i,int j){
return (i-1)*m+j;
}
int dfn[N],low[N],id,vis[N],is[N],tot;
stack<int> s;
void Tarjan(int x){//缩点
dfn[x]=low[x]=++id;
s.push(x);
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[x]=min(low[v],low[x]);
}else if(vis[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
++tot;
while(s.top()!=x){
int temp=s.top();
s.pop();
is[temp]=tot;
vis[temp]=0;
}
int temp=s.top();
s.pop();
is[temp]=tot;
vis[temp]=0;
}
}
int in[N],out[N],tt1,tt2;
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){//建边
for(int j=1;j<=m;j++){
if(i>1&&a[i-1][j]<=a[i][j]){
adding(cal(i,j),cal(i-1,j));
}
if(i<n&&a[i+1][j]<=a[i][j]){
adding(cal(i,j),cal(i+1,j));
}
if(j>1&&a[i][j-1]<=a[i][j]){
adding(cal(i,j),cal(i,j-1));
}
if(j<m&&a[i][j+1]<=a[i][j]){
adding(cal(i,j),cal(i,j+1));
}
}
}
for(int i=1;i<=n*m;i++){
if(!dfn[i]) Tarjan(i);
}
for(int k=1;k<=n*m;k++){//记录入度和出度
for(int i=head[k];i;i=e[i].next){
int v=e[i].to;
if(is[v]!=is[k]){
in[is[v]]++;
out[is[k]]++;
}
}
}
for(int k=1;k<=tot;k++){
if(!in[k]) tt1++;
if(!out[k]) tt2++;
}
if(tot==1){//输出答案
printf("0");
}else{
printf("%d",max(tt1,tt2));
}
return 0;
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

P1653 [USACO04DEC] Cow Ski Area G
https://rechenz.github.io/post/p1653/
作者
热尘
发布于
2023-05-11
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录