CF1131D tarjan，拓扑

题目链接

541div2

http://codeforces.com/contest/1131/problem/D

思路

给出n序列和m序列的相对大小关系

构造出最大值最小的序列

缩点+拓扑

小的向大的连边

相等的连个环

tarjan缩点，判断环内是否ok

最后拓扑

更新要这样

ans[v]=max(ans[v],ans[u]+1);

就是说取最后更新的一个，保证大小关系

代码

#include <bits/stdc++.h>

#define ll long long

#define iter vector<int>::iterator

using namespace std;

const int N=2007;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int M[N][N];

int n,m;

struct node {

	int v,nxt;

}e[N*N];

int head[N*N],tot;

void add(int u,int v) {

	// cout<<u<<" "<<v<<"\n";

	e[++tot].v=v;

	e[tot].nxt=head[u];

	head[u]=tot;

}

vector<int> G[N],col[N];

char s[N];

int dfn[N],low[N],stak[N],top,vis[N],cnt,js,belong[N],rt[N];

int ans[N],ru[N];

void tarjan(int u) {

	 dfn[u]=low[u]=++cnt;

    vis[u]=1;

    stak[++top]=u;

    for(iter v=G[u].begin();v!=G[u].end();++v) {

        if(!dfn[*v]) {

            tarjan(*v);

            dfn[u]=min(dfn[u],dfn[*v]);

        } else

        if(vis[*v])

            dfn[u]=min(dfn[u],low[*v]);

    }

	if(low[u]==dfn[u]) {

		++js;

		while(stak[top]!=u) {

			vis[stak[top]]=0;

			col[js].push_back(stak[top]);

			belong[stak[top]]=js;

			top--;

		}

		top--;

		belong[u]=js;

		vis[u]=0;

		col[js].push_back(u);

	}

}

queue<int> q;

int main() {

	n=read(),m=read();

	for(int i=1;i<=n;++i) {

		scanf("%s",s+1);

		for(int j=1;j<=m;++j) {

			if(s[j]=='>') {

				M[j+n][i]=1;

				M[i][j+n]=-1;

				G[j+n].push_back(i);

				// cout<<j+n<<" "<<i<<"\n";

			}

			if(s[j]=='<') {

				M[i][j+n]=1;

				M[j+n][i]=-1;

				G[i].push_back(j+n);

				// cout<<i<<" "<<j+n<<"\n";

			}

			if(s[j]=='=') {

				G[j+n].push_back(i);

				G[i].push_back(j+n);

			// cout<<j+n<<" "<<i<<"\n";cout<<i<<" "<<j+n<<"?\n";

			}

		}

	}

	// for(int i=1;i<=n+m;++i) {

	// 	for(int j=1;j<=n+m;++j) {

	// 		cout<<M[i][j]<<" ";

	// 	}

	// 	puts("");

	// }

	for(int i=1;i<=m+n;++i)

		if(!dfn[i])

			tarjan(i);

	for(int i=1;i<=js;++i) {

		// cout<<col[i].size()<<"!\n";

		for(iter a=col[i].begin();a!=col[i].end();++a) {

			for(iter b=col[i].begin();b!=col[i].end();++b) {

				// cout<<*a<<" "<<*b<<" ?\n";

				if(M[*a][*b]!=0) {

					// cout<<*a<<" "<<*b<<"\n";

					cout<<"No";

					return 0;

				}

			}

			// cout<<*a<<" ";

		}

		// puts("");

	}

	// return 0;

	for(int i=1;i<=n+m;++i) {

		for(int j=1;j<=n+m;++j) {

			if(M[i][j]==1)

			if(belong[i]!=belong[j]) {

				add(belong[i],belong[j]);

//				cout<<belong[i]<<" "<<belong[j]<<"!!\n";

				ru[belong[j]]++;

			}

		}

	}

//	memset(ans,0x3f,sizeof(ans));

	for(int i=1;i<=js;++i) if(!ru[i]) q.push(i),ans[i]=1;

	while(!q.empty()) {

		int u=q.front();

		q.pop();

		for(int i=head[u];i;i=e[i].nxt) {

			int v=e[i].v;

			ans[v]=max(ans[v],ans[u]+1);

			ru[v]--;

			if(!ru[v]) q.push(v);

		}

	}

//	for(int i=1;i<=js;++i) cout<<ans[i]<<" ";cout<<"\n";return 0;

	puts("Yes");

	for(int i=1;i<=n;++i) printf("%d ",ans[belong[i]]);

	puts("");

	for(int i=1;i<=m;++i) printf("%d ",ans[belong[i+n]]);

	return 0;

}

/*

3 3

<<<

<<=

<<=

*/

巴特西

CF1131D tarjan，拓扑

题目链接

思路

代码

最新文章

热门文章