壹、题面 ¶
§ 1.1.题目背景 §
\(\sf JZM\) 又要去国赛了，但是在去往赛场的时候祂遇到了一个十字路口，这个十字路口包含 \(n\) 个红绿灯，这 \(n\) 个红绿灯有着相同长度的固定的周期 \(T\)，在一个周期中，每个红绿灯恰好一次由红变绿，恰好一次由绿变红（并且都是在整数时刻发生改变）。一个红绿灯如果当前是红色则会显示还需要多久变绿。
由于 \(\sf JZM\) 是神祗，祂仅仅看了 \(m\) 眼就推断出这 \(n\) 个红绿灯的周期 \(T\)，但是，由于 \(\sf Arextre\) 是个废物，他并没有看出来周期，但是他知道神祗的 \(m\) 个数据，他想请你帮他一下忙，判断这些数据是否能够推算出周期 \(T\)，如果可以请输出，否则输出 \(-1\).
§ 1.2.输入输出 §
输入数据
第一行两个整数 \(n,m\)，接下来 \(m\) 行每行 \(n\) 个整数 \(x_{i,j}\) 表示观测结果，\(0\) 表示这
个灯是绿灯，否则表示这个红灯还需要多久会变绿。
保证输入数据合法，即只有可能缺失条件，但不存在两个条件之间存在冲突。
输出数据
一行一个整数表示答案。
样例输入1
4 5
0 33 0 36
0 4 0 7
42 2 42 5
0 21 0 24
8 0 8 54
样例输出1
83
样例输入2
2 2
0 100
100 0
样例输出2
-1
§ 1.3.数据范围 §
对于全部数据，\(1\le nm\le 100000，0\le x_{i,j}\le 10000.\)
不要好奇为什么 \(\sf JZM\) 在一个时刻可以同时看 \(100000\) 个红绿灯并且记录下来，因为
\[\color{red}{\huge\text{祂是神}} \]贰、题解 ¶
绿灯没啥用.
对于同一列来说（即考虑同一个灯），如果有某两个时刻这盏灯都是红灯，那么显然我们可以得到这两行，即这两条信息的时间差，将所有的时间差找出来，如果形成一个收尾相连的环，那么我们就找到其中一个周期，由于题目保证信息相互不冲突，所以，找到最小的周期即为答案。将时间差看成连边，那么我们找的就是环，找环可以使用 \(\tt floyd\) 算法。
考虑这样做的复杂度，建边需要 \(\mathcal O(mn^2)\)，跑 \(\tt floyd\) 的复杂度是 \(\mathcal O(m^3)\)，如果要卡，可以将 \(m\) 开大一点，然后就 \(gg\) 了......
但是可以使用同样的思路，上面找的是 \(m\) 条信息之间的时间循环，我们可以找 \(n\) 个灯的时间循环，具体地，对于同一条信息，我们可以找到两个红灯，显然可以算出他们的红绿灯切换时间差，同样建边，找到连回到第一个灯的环，从中取最小值，我们也可以得到 \(T\)，这样的复杂度就是 \(\mathcal O(nm^2+n^3)\) 咯。
对于 \(n,m\) 择优选择，可以将复杂度控制在 \(\mathcal O(nm\sqrt{nm})\).
一点小优化：
如果我们建图时将权值排序后只连接相邻权值之间的边，那么可以证明两种方法建出来的图中，任意一个简单环的长度都是周期，那么可以 \(\tt dfs\) 求出。这样复杂度就降低到 \(\mathcal O(nm\log n)\).
叁、参考代码 ¶
人太懒了，这是带根的。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
const int maxn=100000;
const int inf=0x3f3f3f3f;
int x[maxn+5], n, m;
inline void input(){
n=readin(1), m=readin(1);
if(n<=m){
for(int i=1; i<=n*m; ++i)
x[i]=readin(1);
}
else{
for(int i=1; i<=m; ++i)
for(int j=1; j<=n; ++j)
x[(j-1)*m+i]=readin(1);
swap(n, m);
}
}
int f[325][325];
inline void getf(){
memset(f, 0x3f, sizeof f);
for(int i=1; i<=m; ++i)
for(int j=1; j<=n; ++j) if(x[(i-1)*n+j])
for(int k=1; k<=n; ++k)
if(x[(i-1)*n+k]>x[(i-1)*n+j])
f[j][k]=min(f[j][k], x[(i-1)*n+k]-x[(i-1)*n+j]);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
for(int k=1; k<=n; ++k)
f[j][k]=min(f[j][k], f[j][i]+f[i][k]);
int ans=0x3f3f3f3f;
for(int i=1; i<=n; ++i)
ans=min(ans, f[i][i]);
if(ans>=1000000000) puts("-1");
else printf("%d\n", ans);
}
signed main(){
freopen("crossing.in", "r", stdin);
freopen("crossing.out", "w", stdout);
input();
getf();
return 0;
}
肆、用到 の \(\tt trick\) ¶
时间周期？和环可能有莫大关联呢.