网站模板建站公司,创新的营销型网站,wordpress路径优化,公司网页制作流程problem
题目描述
给定一张 nnn 个点的无向图#xff0c;定义经过一个点 uuu 的非平凡回路为一条从 uuu 出发回到 uuu 的路径#xff0c;并且至少包含一个简单环。
对于每个点求出经过它的最小非平凡回路长度 lll。
考虑到这个问题很困难#xff0c;因此你只需要求出 ⌈…problem
题目描述
给定一张 nnn 个点的无向图定义经过一个点 uuu 的非平凡回路为一条从 uuu 出发回到 uuu 的路径并且至少包含一个简单环。
对于每个点求出经过它的最小非平凡回路长度 lll。
考虑到这个问题很困难因此你只需要求出 ⌈l2⌉\lceil\frac{l}{2}\rceil⌈2l⌉ 即可。特别地如果不存在经过它的非平凡回路则输出 −1-1−1。
这里的简单环定义为环上边各不相同。
输入格式
第一行一个正整数 nnn。
接下来 n−1n-1n−1 行。第 iii 行有一个长度为 iii 的 010101 串表示 i1i1i1 号点和 1∼i1\sim i1∼i 号点是否有边。
输出格式
共 nnn 行表示答案。
数据范围
n≤5000n\le 5000n≤5000。
solution
这道题挺有迷惑性的。
看这个 nnn 的范围明显连 n2n^2n2 的算法都能接受肯定不会是考察什么高级算法带 logloglog 的。
考虑暴力就是从每个点开始 bfsbfsbfs 搜答案当第二次访问到一个点时则为有环。
很可惜时间复杂度是 O(nm)O(nm)O(nm)边数 mmm 又是 n2n^2n2 级别的。
我们希冀找到一种解法的时间复杂度只和点数 nnn 挂钩。
仍然是 bfsbfsbfs。
对于每个点 uuu 记录其前驱点由哪个点转移过来的lstulst_ulstu。
然后遍历所有和 uuu 有边相连的点 vvv如果 vvv 已经被访问过了且不是 uuu 的前驱则答案为 disu1dis_u1disu1。
这样子如果一个点被访问两次就会结束 bfsbfsbfs最坏情况下就是把 nnn 个点都访问了一次下一次就一定会结束抽屉原理。
时间复杂度自然只和点数挂钩O(n2)O(n^2)O(n2)。
答案为什么为 disu1dis_u1disu1 因为是最短路 bfsbfsbfs所以一个环一定是从某个点进入然后两边开始遍历的即只用环长 ⌈l2⌉\lceil\frac l2\rceil⌈2l⌉ 层就能遍历环上所有点。 这个 uuu 肯定是连接两个相反方向遍历最新经过点的点。 奇偶环的问题导致非平凡回路的长度不同但是答案形式变化后就是一样的了。
code
#include bits/stdc.h
using namespace std;
#define maxn 5005
int n;
char s[maxn];
int dis[maxn], lst[maxn];
vector int G[maxn];
queue int q;void bfs( int x ) {memset( dis, -1, sizeof( dis ) );memset( lst, -1, sizeof( lst ) );while( ! q.empty() ) q.pop();dis[x] 0; q.push( x );while( ! q.empty() ) {int u q.front(); q.pop();for( int v : G[u] ) if( ~ dis[v] ) {if( lst[u] v ) continue;else { printf( %d\n, dis[u] 1 ); return; }}else {dis[v] dis[u] 1;lst[v] u;q.push( v );}}puts(-1);
}int main() {scanf( %d, n );for( int i 2;i n;i ) {scanf( %s, s 1 );for( int j 1;j i;j )if( s[j] - 0 ) {G[j].push_back( i );G[i].push_back( j );}}for( int i 1;i n;i ) bfs( i );return 0;
}
