tarjan 45pt 3RE 2WA求调
查看原帖
tarjan 45pt 3RE 2WA求调
308800
Polynswin楼主2024/7/20 16:11
#include<bits/stdc++.h>
#define mmt(a,b) memset(a,b,sizeof(a))
#define test(x) cout<<#x<<" = "<<x<<endl
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define endl '\n'
#define enter putchar(endl)
//#define int long long
using namespace std;
inline void read(int &x);
inline void ffout(int x);
inline void ffout(string b);
inline void ffout(int x,char b);
inline void ffout(int x,string b);
inline void print(string name,int a[],int r);
const int inf=0x3f3f3f3f,N=5e2+10;
const int p[5]={0,1,0,-1,0};
int n,l,w,tot1,tot2,timestamp,scc_cnt;
int in[N],out[N];
int dfn[N][N],low[N][N],a[N][N],scc[N][N];
bool to[N][N],in_stk[N][N];
vector<int> G[N];
void add(int u,int v)
{
	G[u].push_back(v);
}
struct node{
	int x,y;
};
stack<node> stk;
void tarjan(int x,int y)
{
	dfn[x][y]=low[x][y]=++timestamp;
	stk.push(node({x,y}));
	in_stk[x][y]=true;
	for(int i=1;i<=4;i++)
	{
		int tx=x+p[i],ty=y+p[i-1];
		if(tx>l||tx<1||ty>w||ty<1||a[x][y]<a[tx][ty])continue;
		if(!dfn[tx][ty])
		{
			tarjan(tx,ty);
			low[x][y]=min(low[x][y],low[tx][ty]);
		}
		else if(in_stk[tx][ty])low[x][y]=min(low[x][y],dfn[tx][ty]);
	}
	if(dfn[x][y]==low[x][y])
	{
		node sx;
		scc_cnt++;
		do{
			sx=stk.top();
			stk.pop();
			scc[sx.x][sx.y]=scc_cnt;
			in_stk[sx.x][sx.y]=false;
		}while(sx.x!=x||sx.y!=y);
	}
}
signed main()
{
	int i,j,k;
	cin>>w>>l;
	for(i=1;i<=l;i++)
		for(j=1;j<=w;j++)
			cin>>a[i][j];
	for(i=1;i<=l;i++)
		for(j=1;j<=w;j++)
			if(!dfn[i][j])tarjan(i,j);
	for(i=1;i<=l;i++)
		for(j=1;j<=w;j++)
			for(k=1;k<=4;k++)
			{
				int tx=i+p[k],ty=j+p[k-1];
				if(tx>l||tx<1||ty>w||ty<1||a[i][j]<a[tx][ty])continue;
				int scc1=scc[i][j],scc2=scc[tx][ty];
				if(!to[scc1][scc2])
				{
					add(scc1,scc2);
					in[scc2]++;
					out[scc1]++;
					to[scc1][scc2]=true;
				}
			}
	for(i=1;i<=scc_cnt;i++)
	{
		if(!in[i])tot1++;
		if(!out[i])tot2++;
	}
	ffout(max(tot1,tot2));
	return 0;
}









inline void ffout(string b)
{
	int len=b.size();
    for(int i=0;i<len;++i)putchar(b[i]);
}
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x=x*f;
}
inline void ffout(int x)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
}
inline void ffout(int x,char b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    putchar(b);
}
inline void ffout(int x,string b)
{
    if(x<0){x=-x; putchar('-'); }
    short sta[63],top=0;
    do{ sta[top++]=x%10; x/=10; }while(x);
    while(top) putchar(sta[--top]+'0');
    ffout(b);
}
inline void print(string name,int a[],int r)
{
	ffout(name);
	putchar(':');
	for(int i=1;i<=r;i++)
		ffout(a[i],' ');
	putchar(endl);
}





2024/7/20 16:11
加载中...