//卡了一个上午真是爽死了
大神请右上角
好，废话不多说，上题面
Cow Ski Area
Description
Farmer John's cousin, Farmer Ron, who lives in the mountains of Colorado, has recently taught his cows to ski. Unfortunately,
his cows are somewhat timid and are afraid to ski among crowds of people at the local resorts, so FR has decided to construct his own private ski area behind his farm.
FR's ski area is a rectangle of width W and length L of 'land squares' (1 <= W <= 500; 1 <= L <= 500). Each land square is an integral height H above sea level (0 <= H <= 9,999). Cows can ski horizontally and vertically between any two adjacent land squares, but never diagonally. Cows can ski from a higher square to a lower square but not the other way and they can ski either direction between two adjacent squares of the same height.
FR wants to build his ski area so that his cows can travel between any two squares by a combination of skiing (as described above) and ski lifts. A ski lift can be built between any two squares of the ski area, regardless of height. Ski lifts are bidirectional. Ski lifts can cross over each other since they can be built at varying heights above the ground, and multiple ski lifts can begin or end at the same square. Since ski lifts are expensive to build, FR wants to minimize the number of ski lifts he has to build to allow his cows to travel between all squares of his ski area.
Find the minimum number of ski lifts required to ensure the cows can travel from any square to any other square via a combination of skiing and lifts.
Input
* Line 1: Two space-separated integers: W and L
* Lines 2..L+1: L lines, each with W space-separated integers corresponding to the height of each square of land.
Output
* Line 1: A single integer equal to the minimal number of ski lifts FR needs to build to ensure that his cows can travel from any square to any other square via a combination of skiing and ski lifts
Sample Input
9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1
Sample Output
3
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
OUTPUT DETAILS:
FR builds the three lifts. Using (1, 1) as the lower-left corner,
the lifts are (3, 1) <-> (8, 2), (7, 3) <-> (5, 2), and (1, 3) <->
(2, 2). All locations are now connected. For example, a cow wishing
to travel from (9, 1) to (2, 2) would ski (9, 1) -> (8, 1) -> (7,
1) -> (7, 2) -> (7, 3), take the lift from (7, 3) -> (5, 2), ski
(5, 2) -> (4, 2) -> (3, 2) -> (3, 3) -> (2, 3) -> (1, 3), and then
take the lift from (1, 3) - > (2, 2). There is no solution using
fewer than three lifts.
//你是想让我们想象奶牛滑雪的样子吗？？！！抱歉我想象不出
题木大衣：
奶牛要滑雪，只能从高的地方滑到低的地方(高度相同也可以)。现在你要装滑雪电梯，滑雪电梯可以连接任意两个点。求最少要装几个才能使得任意两点之间都能互相到达
这种傻吊题，先强连通缩点，如果缩完后只剩一个点了，则输出0，否则ans=max(入度为0的点数，出度为0的点数)
于是傻傻的我立刻入手做了~
先DFS缩点~再连边~
马上过了样例~
然后我就发现500x500的数据DFS爆栈了，于是就控制了下深度
由于我是构完DAG图再扫解的，于是我发现最坏的情况下，，，点的个数最多有250000个0 0，然后我是开的邻接矩阵……
不说了，第一次交WA
第二次RE，第三次超内存……
然后我要压空间~，开布尔型数组可以开到30000x30000然后我的DAG数组只记录每个点的入度出度数
但是……这也是明显会RE的。。。
怎么办呢，，，我发现，如果这个点出度入度都大于0了的话这个点便不用管了0 0
于是我把f布尔型数组开了250000*2。。记录该点是否出入（表误会）过，，，于是，于是~
我就TLE了
Time Limit Exceeded
于是我开始优化时间时间时间时间时间时间时间
……过了很久
傻傻的我想到0 0，我这方法是n²的啊不可能超时
然后我发现了一件自扇巴掌的事实：劳资忘去掉freopen了！！
……过了很久
傻傻的我想到0 0，我这方法是n²的啊不可能超时
然后我发现了一件自扇巴掌的事实：劳资忘去掉freopen了！！
/*强连通缩点0 0表学我滥用define*/
#include<cstdio>
using namespace std;
#define max(a,b) (a>b?a:b)
#define f0(x,y) f[map[x][y]][0]=1
#define f1(x,y) f[map[x][y]][1]=1
#define fdag(x,y,z) (++dag[map[x][y]][z])
#define up (x>1&&map[x-1][y]!=map[x][y]&&a[x-1][y]<a[x][y]&&(!f[map[x][y]][0]||!f[map[x-1][y]][1]))
#define down (x<n&&map[x+1][y]!=map[x][y]&&a[x+1][y]<a[x][y]&&(!f[map[x][y]][0]||!f[map[x+1][y]][1]))
#define left (y>1&&map[x][y-1]!=map[x][y]&&a[x][y-1]<a[x][y]&&(!f[map[x][y]][0]||!f[map[x][y-1]][1]))
#define right (y<m&&map[x][y+1]!=map[x][y]&&a[x][y+1]<a[x][y]&&(!f[map[x][y]][0]||!f[map[x][y+1]][1]))
int m,n,k,jsj,b;
int map[500+1][500+1],a[500+1][500+1],dag[250000+1][2];
bool f[250000+1][2];
inline int read(){
char ch;int a=0;bool f=false;
ch=getchar();
while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
if(ch!='-')a*=10,a+=ch-'0';else f=true;
while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
if(f)a=-a;
return a;
}
inline void getmap(int x,int y){
if(map[x][y])return;
if(jsj==2500){
b=1;
return;
}
map[x][y]=k;++jsj;
if(x-1>=1&&a[x-1][y]==a[x][y])getmap(x-1,y);
if(x+1<=n&&a[x+1][y]==a[x][y])getmap(x+1,y);
if(y-1>=1&&a[x][y-1]==a[x][y])getmap(x,y-1);
if(y+1<=m&&a[x][y+1]==a[x][y])getmap(x,y+1);
}
inline void build(int x,int y){
if(up)f0(x,y),f1(x-1,y),fdag(x,y,0),fdag(x-1,y,1);
if(down)f0(x,y),f1(x+1,y),fdag(x,y,0),fdag(x+1,y,1);
if(left)f0(x,y),f1(x,y-1),fdag(x,y,0),fdag(x,y-1,1);
if(right)f0(x,y),f1(x,y+1),fdag(x,y,0),fdag(x,y+1,1);
}
int main(){
m=read(),n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
k=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!map[i][j]){
++k;jsj=b=0;
getmap(i,j);
if(b)--k;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!f[map[i][j]][0])build(i,j);
int in=0,out=0;
for(int i=1;i<=k;i++){
if(dag[i][0]==0)out++;
if(dag[i][1]==0)in++;
}
if(k==1)printf("0");else
printf("%d",max(in,out));
}
loading...
评论 (0)
