CF1810E 题解

一、题目描述：

　　给你一个 n 个点，m 条边的无向图，点带权，起点可任意选择。

　　每走过一个新的点，你的能力值会 +1 。一开始你的能力值为 0 。

　　你只能经过点权小于等于你能力值的点。每条边，每个点都可以经过无限次，问能否走遍整个图。

　　如果可以，输出 "YES" 。否则输出 "NO" 。有 t 组数据，保证 n 的总和，m 的总和都不超过 2e5 ，t <= 1e3 。

二、做题思路：

　　很明显，你只能选择点权为 0 的点作为起点。枚举每个点权为 0 的点，跑一边 dij ，时间复杂度 O(n*nlogm)，显然超时。

　　考虑优化，之前已经访问过的点再用作起点肯定不优（这里不做解释）。用一个 vis 数组标一下。

　　每次 dij 不能 O(n) 的初始化，判定一个点 u 这一轮是否访问过的时候可以判 if (vis[u]==s)，其中 s 为起点。

　　现在时间复杂度已经是 O(nlogm) 了。复杂度不好直接说明，放个图：

　　假设一开始枚举的点是中间那个 0 ，一共可以拓展到 4 个点 (红点) 。周围被点权较大的点所包围，无法再拓展。

　　如果重复拓展到这几个点，那么一定是经过了点权较大的点，此时经过的点 (蓝点) 一定大于 4 个 ，才能通过点权较大的点。

　　由此可以发现，总拓展点数最大为 n+n/2+n/4+n/8+...，小于等于 2n 。时间复杂度最差 O(2nlogm)，可以通过。

三、完整代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 #define N 200010
 5 using namespace std;
 6 int T,n,m,u1,v1,now,c[N],vis[N];
 7 struct EDGE{
 8     int v,nxt;
 9 }edge[N*2];
10 int head[N],cnt;
11 void add(int u,int v)
12 {
13     edge[++cnt].v=v;
14     edge[cnt].nxt=head[u];
15     head[u]=cnt;
16 }
17 struct node{
18     int pos,dis;
19     bool operator < (const node &t)const{
20         return t.dis<dis;
21     }
22 };
23 priority_queue <node> q;
24 int dij(int s)
25 {
26     while(!q.empty())
27         q.pop();q.push({s,0});now=0;
28     while(!q.empty())
29     {
30         int u=q.top().pos;q.pop();
31         if(vis[u]==s)    continue;vis[u]=s;
32         if(now<c[u])    return 0;    now++;
33         for(int i=head[u];i!=-1;i=edge[i].nxt)
34             q.push({edge[i].v,c[edge[i].v]});
35     }
36     return now==n;
37 }
38 void solve()
39 {
40     cin>>n>>m;cnt=0;
41     for(int i=1;i<=n;i++)
42     {
43         cin>>c[i];
44         head[i]=-1,vis[i]=0;
45     }
46     for(int i=1;i<=m;i++)
47     {
48         cin>>u1>>v1;
49         add(u1,v1),add(v1,u1);
50     }
51     for(int i=1;i<=n;i++)
52         if(!c[i]&&!vis[i]&&dij(i))
53         {
54             cout<<"YES"<<'\n';
55             return ;
56         }
57     cout<<"NO"<<'\n';
58 }
59 int main()
60 {
61     ios::sync_with_stdio(false);
62     cin.tie(0);cout.tie(0);
63     cin>>T;
64     for(int i=1;i<=T;i++)
65         solve();
66     return 0;
67 }

四、写题心得：

　　这个题写起来不难，就是时间复杂度难以证明。不过自己花了这么多时间证出来了（头一次配了图 ! ），也是真的很高兴。拜拜！