题意：给你一个n*m的矩阵，需要在不改变每一行和每一列的大小关系的情况下压缩一个矩阵，压缩后的矩阵所有数的总和尽量的小。
思路：我们有这样的初步设想：对于在一行或一列的数x,y,若x<y，则建立一条x的位置到y的位置的边。之后进行拓扑排序的DP即可。然而会被卡边数卡掉，所以需要其它的解法。
新思路：我们把所有的数排个序，这样方便选对所有相同的数赋值。我们从小到大对所有的数赋值，合并这个数所在的行和列，选取相关的行和列中的最大值+1作为作为这个数的新值。
为什么这样做正确呢？可以类比拓扑排序的dp过程，我们所赋的新值不能破坏原来行和列的大小关系，所以要找相关的行和列中的最大值+1。用并查集可以快速判断哪些行和列相关。
实现参考了fateice大神的代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
int ans[maxn],x[maxn],y[maxn],f[maxn],mx[maxn];
struct node{
int x,y,val,pos;
bool operator <(const node& rhs)const{
return val<rhs.val;
}
};
node a[maxn];
int n,m;
int num(int i,int j){
return (i-1)*m+j;
}
inline int get(int x){
if(x==f[x])return x;
return f[x]=get(f[x]);
}
void merge(int x,int y){
f[get(x)]=get(y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int pos=num(i,j);
scanf("%d",&a[pos].val);
a[pos].x=i,a[pos].y=j,a[pos].pos=pos;
}
sort(a+1,a+1+n*m);
for(int i=1;i<=n+m;i++)
f[i]=i;
int i,j,k;
for(i=1;i<=n*m;i=j){
for(j=i;a[j].val==a[i].val&&j<=n*m;j++);
for(k=i;k<j;k++)merge(a[k].x,a[k].y+n);
for(k=i;k<j;k++){
int tmp=get(a[k].x);
mx[tmp]=max(mx[tmp],max(x[a[k].x],y[a[k].y]));
}
for(k=i;k<j;k++){
ans[a[k].pos]=mx[get(a[k].x)]+1;
x[a[k].x]=ans[a[k].pos];
y[a[k].y]=ans[a[k].pos];
}
for(k=i;k<j;k++){
mx[a[k].x]=0;
f[a[k].x]=a[k].x;
mx[a[k].y+n]=0;
f[a[k].y+n]=a[k].y+n;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",ans[num(i,j)]);
}
printf("
");
}
return 0;
}