*题解：Gym104197D Distance Parities

题目链接

解析

对于 \(a_{i,j} = 0\)，\(i,j\) 之间必定没有连边。由于图是联通的，于是存在 \(k\) 使得 \(a_{i,k} = a_{k,j} = 1\) 为 \(a_{i,j} = 0\) 的充要条件，而让 \(a_{i,k}=1\) 的最简单的办法就是令 \(d_{i,j} = 1\)，即建一条连接 \(i,k\) 的边。按照这种方式连边，显然能满足所有 \(a_{i,j} = 1\) 的位置。要判断能否满足 \(a_{i,j} = 0\) 的位置，只需把边连上之后跑 Floyd 求最短路再进行判断即可。

时间复杂度 \(O(n ^ 3)\)。

实际上这个过程可以用 bitset 优化，利用前面所说的充要条件，将 \(a_i\) 和 \(a_j\) 看成两个 bitset，要判断的就是 \(a_i \operatorname{and} a_j\) 中是否存在 \(1\)。

时间复杂度 \(O(\frac{n ^ 3}{w})\)。

代码

/*
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
using namespace std;
typedef long long ll;
typedef unsigned ui;
typedef pair<ll, ll> pii;
const int N = 2000 + 5, M = 20, P = 450, mod = 1e9 + 7, mod2 = 1e9 + 7, b1 = 131;
int a[N][N],d[N][N];
signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);int T;cin>>T;while(T--){int n;cin>>n;vector<pii> v;bitset<2000> d[n + 5];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char ch;	cin>>ch;a[i][j] = ch - '0';d[i][j] = a[i][j];if(a[i][j] == 1 && j > i){v.push_back({i,j});}}}bool flag = true;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){flag &= (d[i] & d[j]).any() || d[i][j];}}if(flag){cout<<"YES\n";cout<<v.size()<<'\n';for(int i=0;i<v.size();i++){cout<<v[i].first<<" "<<v[i].second<<'\n';}}else{cout<<"NO\n";}}return 0;
}