Codeforces Round #836 (Div. 2) E.Tick, Tock(在线:带权并查集/离线:dfs判环)

题目

n*m(1<=n,m<=2e5,n*m<=2e5)的网格图，

有一些格子内已经放入了闹钟，当前时刻在[0,h)(1<=h<=1e9)之间

还有一些位置没有放闹钟，输入时用-1表示，

在放入这些闹钟的时候，你可以指定它们的初始时刻，只要在[0,h)即可

不同的闹钟，被指定的初始时刻可以不同

放完这些闹钟之后，你可以执行以下操作若干次，

每次选择一行或者一列，并将这些闹钟都往后调一个小时，

即，当前闹钟时刻x，x<h-1时，会被调到x+1；x=h-1时，会被调到0

求指定初始时刻的方案数，使得所有的闹钟可以被调到同一时刻，答案对1e9+7取模

实际用例总数t不超过5e4，但保证sum n*m<2e5

思路来源

乱搞ac

题解

其实和刚刚的abc280f很像，只是这个题更直接一些，

都有在线和离线两种做法，感觉很典中典

在线：带权并查集(hdu3047)；离线：建树然后dfs判环(abc280f)

而abc280f这个题，主要是要找出非零环，

于是对图dfs得到一棵树后，检查非树边是否可以被树边线性表示

这个题也可以采用一样的做法，将同一行内的，值不为-1的两列，x列和y列，

连边y->x，权值(val[y]-val[x])%h；连边x->y，权值(val[x]-val[y])%h，就化成了abc280f这个题

于是只需检查，不同行对于列的限制，是否存在矛盾即可

对每一行做完之后，每一列就无需再做一遍了，

因为如果行的限制满足，势必存在一个delta，

使得第一行的x列的数，加delta后，等于第二行的x列的数；

第一行的y列的数，加delta后，等于第二行的y列的数；

检查完没有矛盾之后，

对于确定的数(不是-1的数)所在的位置(x,y)，就直接将x行和y列这两个点直接连到一起，

连到一起后，当前图相当于被分成了若干个连通块，

而每将-1填成一个具体的数，都有h种选择，

并且，将(x,y)处的-1填成具体数后，

相当于将x行所在的联通和y列所在的连通块合并到一起

最后，需要将n行m列这n+m个点合并成一个连通块

设通过-1合并了x次，则答案为h的x次方，

感觉有点类似矩阵的秩

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=4e5+10,mod=1e9+7;
int t,n,m,h,par[maxn];
ll pos[maxn];
void init(int x){
	for(int i=0;i<x;++i){
		par[i]=i;
		pos[i]=0;
	}
}
int find(int x){
	if(par[x]==x)return x;
	int fa=par[x];//直接基类 
	par[x]=find(par[x]);//路径压缩 
	(pos[x]+=pos[fa])%=h;//树上前缀和 两链变一链 直接连树根 
	return par[x];//返回树根 
}
//y比x大v 
bool unite(int x,int y,ll v){
	int px=find(x),py=find(y);
	if(px==py){
		if((pos[x]+v-pos[y])%h)return 0;
		return 1;
	}
	//把y所在树的树根挂在x所在树的树根上 只改树根py 
	par[py]=px;//rank[py]=rank[y现在]-rank[y之前]==(rank[x]+v)-rank[y] 
	pos[py]=((pos[x]+v-pos[y])%h+h)%h;//注意rank可能有负 与将负旋为0的根是等价的
	return 1; 
} 
int solve(){
    vector<vector<ll> >a(n+1,vector<ll>(m+1,0));
    int all=0,cnt=0;
    init(m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            scanf("%lld",&a[i][j]);
        }
    }
    for(int i=0;i<n;++i){
        int las=-1;
        for(int j=0;j<m;++j){
            if(a[i][j]==-1)continue;
            if(~las && !unite(las,j,(a[i][j]-a[i][las]+h)%h)){
                return 0;
            }
            las=j;
        }
    }
    /*
    init(n);
    for(int j=0;j<m;++j){
        int las=-1;
        for(int i=0;i<n;++i){
            if(a[i][j]==-1)continue;
            if(~las && !unite(las,i,a[i][j]-a[las][j])){
                return 0;
            }
            las=i;
        }
    }*/
    init(n+m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(~a[i][j])par[find(n+j)]=find(i);
        }
    }
    for(int i=0;i<n+m;++i){
        if(find(i)==i)cnt++;
    }
    int res=1;
    for(int i=1;i<cnt;++i){
        res=1ll*h*res%mod;
    }
    //printf("res:%d h:%d\n",res,h);
    //printf("res:%d\n",res);
    return res;
}
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;++i){
        scanf("%d%d%d",&n,&m,&h);
        printf("%d\n",solve());
    }
	return 0;
} 
/*
hdu3047 带权并查集
1 2
-1 -1

1 -1
-1 2

1 0 -1
-1 -1 2

n+m-1个点 现在有3个点

-1 -1 -1
-1 -1 -1
n+m-1个点 现在有0个点
*/