【Codeforces 650C】Table Compression

  对原图建DAG限制同行同列点的大小关系，将同行或同列中相等的点并成一个点，然后跑一遍最长路就好了。初始入度为0的点大小设为1.

  缩点我想了一下用并查集缩。然后我就打了个Spfa并打错了并查集，人不能更傻了。

  正解是类似拓扑排序跑一遍。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000010;

#define p(x,y) (((x)-1)*m+(y))

struct Node
{
	int v,id;
}P[maxn];

int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
int deg[maxn];
int fa[maxn];
int map[maxn];
int n,m,S,ans;

bool cmp(const Node &a,const Node &b) {return a.v<b.v;}
void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;}
int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}

int Q[maxn],top,tail;
int dis[maxn];

void TP()
{
	Q[top=tail=1]=S;
	while (top<=tail)
	{
		int x=Q[top++];
		for (int i=head[x];i;i=next[i])
		{
			dis[E[i]]=max(dis[E[i]],dis[x]+1);
			deg[E[i]]--;
			if (deg[E[i]]==0) Q[++tail]=E[i];
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&map[p(i,j)]);
	for (int i=1;i<=n*m;i++) fa[i]=i;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) P[j].v=map[p(i,j)],P[j].id=j;
		sort(P+1,P+1+m,cmp);
		for (int j=1;j<m;j++) if (P[j].v==P[j+1].v) fa[Find(p(i,P[j].id))]=Find(p(i,P[j+1].id));
	}
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++) P[j].v=map[p(j,i)],P[j].id=j;
		sort(P+1,P+1+n,cmp);
		for (int j=1;j<n;j++) if (P[j].v==P[j+1].v) fa[Find(p(P[j].id,i))]=Find(p(P[j+1].id,i));
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) P[j].v=map[p(i,j)],P[j].id=j;
		sort(P+1,P+1+m,cmp);
		for (int j=1;j<m;j++) if (P[j].v<P[j+1].v) Add_Edge(Find(p(i,P[j].id)),Find(p(i,P[j+1].id))),deg[Find(p(i,P[j+1].id))]++;
	}
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++) P[j].v=map[p(j,i)],P[j].id=j;
		sort(P+1,P+1+n,cmp);
		for (int j=1;j<n;j++) if (P[j].v<P[j+1].v) Add_Edge(Find(p(P[j].id,i)),Find(p(P[j+1].id,i))),deg[Find(p(P[j+1].id,i))]++;
	}
	S=n*m+1;
	for (int i=1;i<=n*m;i++) if (Find(i)==i && deg[i]==0) Add_Edge(S,i),deg[i]++;
	TP();
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) printf("%d%c",dis[Find(p(i,j))],(j==m)?'\n':' ');
	return 0;
}