Problem
Sajin最近深入研究了最小生成树，现在他已经掌握了MST的算法。他渴望通过一系列查询来评估您对最小生成树概念的掌握程度。
您将面临一个加权无向图，该图包含没有任何自环的 \(n\) 个顶点和 \(m\) 条边。
Sajin提出 \(q\) 询问。对于每个顶点集，都给出了一个顶点集 \(S\) 。您的目标是确定 \(S\) 的诱导子图（induced subgraph）并找到其最小生成树的权重。如果 \(S\) 的诱导子图断开，则输出-1。
图的诱导子图是另一个图，由图的顶点子集和原始图中的所有边组成，连接该子集中的顶点对。即，对于图 \(G=(V,E)\) ，给定 \(V^\prime\) ，则有 \(E^\prime=\{(u,v) \mid u,v\in V^\prime,(u,v)\in E\}\)，诱导子图为 \(G^\prime=(V^\prime,E^\prime)\)。
\(2\le n\le 10^5,1\le m,q\le10^5\)
\(1 \le |S_i|\le n,\sum S_i\le 10^5\)
Solution
Algorithm1
由于限制了 \(\sum S_i\le 10^5\) ， MST本身的时间复杂度是完全过得去的。但是瓶颈在于如何从 \(G\) 中挑出需要的边。
考虑两种找边的方法：
- 对于 \(S\) 中的点 \(x\)，遍历 \(x\) 的所有出边，终点为 \(y\) 。如果 \(y\in S\) ，那么边 \((x,y)\in G^\prime\) 。将得到的所有边存起来并排序跑kruskal。
对于一次询问，这个算法的最坏时间复杂度为 \(O(m\log(|S|))\) ，即所有边都需要被遍历一次。
- 用map存图 \(G\) ；双重遍历 \(x,y\in S\) ，将其中存在的边 \((x,y)\) 取出来并排序跑kruskal。
整体时间复杂度是\(O(n^2+n^2\log(n))\)，即双重遍历和kruskal。
取 \(base=\sqrt n\) ，
- 当 \(|S|\le base\) 时使用第二种算法，总时间复杂度为 \(O(n\cdot base\cdot \log(n))\)
- 当 \(|S| > base\) 时使用第一种算法，总时间复杂度为 \(O(base\cdot m\cdot \log(n))\)
Algorithm2
一般建立最小生成树，我们会使用上面的第一种找边的方式：对于 \(S\) 中的点 \(x\)，遍历 \(x\) 的所有出边，终点为 \(y\) 。如果 \(y\in S\) ，那么边 \((x,y)\in G^\prime\) 。将得到的所有边存起来并排序跑kruskal。
问题的瓶颈在于新建导出子图 \(G^\prime\) 的时候，会被类菊花图卡掉。可能会一直询问类菊花图的核心点，而这些核心点具有很多条出边，每次询问都需要遍历核心节点的出边。
考虑类似三元环的连边方式，对于每条边，只从度小的点到度大的点连一条单向边。如果度数相同，则从编号小的连接到编号大的。
在这样构建的图中，每个点的出度不会大于 \(\sqrt m\) 。如果有某个点的出度为 \(d > \sqrt m\) ，那么在原图中，需要有 \(d\) 个度数大于 \(d\) 的节点与该节点连接，此时总边数至少 \(d\times d>m\)，矛盾。
所以可以在这样的一张单向图中放心的找边，单次询问时间复杂度 \(O(|S| \sqrt m \log(|S|))\) 。
Code
Code1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| #define N 100010
struct Edge
{
int x,y;
LL w;
Edge(int xx,int yy,LL ww)
{
x=xx;
y=yy;
w=ww;
}
bool operator<(const Edge & z)
{
return w<z.w;
}
};
int n,m,q;
namespace algo1{
int cnt;
int head[N],nxt[N*2],ver[N*2],w[N*2];
void insert(int x,int y,LL z)
{
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
w[cnt]=z;
}
};
namespace algo2{
map<pii,LL>mp;
void insert(int x,int y,LL z)
{
pii e=make_pair(x,y);
if(mp.find(e)==mp.end()) mp[e]=z;
else mp[e]=min(mp[e],z);
}
bool exist(pii e)
{
return mp.find(e)!=mp.end();
}
};
namespace DSU{
int vis[N],f[N],sz[N];
int getf(int x)
{
if(x==f[x]) return x;
return f[x]=getf(f[x]);
}
void merge(int x,int y)
{
x=getf(x);
y=getf(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
f[y]=x;
sz[x]+=sz[y];
}
bool ask(int x,int y)
{
return getf(x)==getf(y);
}
};
LL MST(vector<int>V,vector<Edge>E)
{
sort(E.begin(),E.end());
LL ans=0;
int cnt=1;
for(unsigned int i=0;i<E.size();i++)
{
if(!DSU::ask(E[i].x,E[i].y))
{
cnt++;
DSU::merge(E[i].x,E[i].y);
ans+=E[i].w;
}
}
if(cnt!=V.size()) return -1;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
while(t--)
{
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int x,y;
LL z;
cin>>x>>y>>z;
algo1::insert(x,y,z);
algo1::insert(y,x,z);
algo2::insert(x,y,z);
algo2::insert(y,x,z);
}
const int base=sqrt(100000);
while(q--)
{
int k;
cin>>k;
vector<int>S;
vector<Edge>E;
for(int i=0;i<k;i++)
{
int t;cin>>t;
S.push_back(t);
DSU::vis[t]=1;
DSU::sz[t]=1;
DSU::f[t]=t;
}
if(k>base)
{
for(int i=0;i<k;i++)
{
int x=S[i];
for(int j=algo1::head[x];j;j=algo1::nxt[j])
{
int y=algo1::ver[j];
LL w=algo1::w[j];
if(DSU::vis[y])
{
E.push_back(Edge(x,y,w));
}
}
}
}
else
{
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
pii e=make_pair(S[i],S[j]);
if(algo2::exist(e))
{
E.push_back(Edge(S[i],S[j],algo2::mp[e]));
}
}
}
}
cout<<MST(S,E)<<endl;
for(int i=0;i<k;i++)
{
DSU::vis[S[i]]=0;
}
}
}
return 0;
}
|
生最差劲的一件事莫过于早上写的代码但半路跑路还没做任何标记，晚上打开不知道从何续写。
人生最美好的一件事莫过于发现这份代码其实是以及写完的！？而且还能过样例！？？而且直接提交直接过了！？？？
Code2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
| #define N 100010
struct Edge
{
int x,y;
LL w;
Edge(int xx,int yy,LL ww)
{
x=xx;
y=yy;
w=ww;
}
bool operator<(const Edge & z)
{
return w<z.w;
}
};
int n,m,q;
namespace G1
{
map<pii,LL>mp;
int degree[N];
void insert(int x,int y,LL z)
{
pii e=make_pair(x,y);
if(mp.find(e)==mp.end()) mp[e]=z;
else mp[e]=min(mp[e],z);
degree[x]++;
}
};
namespace G2
{
int cnt;
int head[N],nxt[N*2],ver[N*2];
LL w[N];
void insert(int x,int y,LL z)
{
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
w[cnt]=z;
}
};
namespace DSU{
int vis[N],f[N],sz[N];
int getf(int x)
{
if(x==f[x]) return x;
return f[x]=getf(f[x]);
}
void merge(int x,int y)
{
x=getf(x);
y=getf(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
f[y]=x;
sz[x]+=sz[y];
}
bool ask(int x,int y)
{
return getf(x)==getf(y);
}
};
LL MST(vector<int>V,vector<Edge>E)
{
sort(E.begin(),E.end());
LL ans=0;
int cnt=1;
for(unsigned int i=0;i<E.size();i++)
{
if(!DSU::ask(E[i].x,E[i].y))
{
cnt++;
DSU::merge(E[i].x,E[i].y);
ans+=E[i].w;
}
}
if(cnt!=V.size()) return -1;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
while(t--)
{
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int x,y;
LL z;
cin>>x>>y>>z;
G1::insert(x,y,z);
G1::insert(y,x,z);
}
for(auto it=G1::mp.begin();it!=G1::mp.end();it++)
{
int x=it->first.first,y=it->first.second;
LL w=it->second;
if(G1::degree[x]<G1::degree[y]||(G1::degree[x]==G1::degree[y]&&x<y)) G2::insert(x,y,w);
}
while(q--)
{
int k;
cin>>k;
vector<int>S;
vector<Edge>E;
for(int i=0;i<k;i++)
{
int t;cin>>t;
S.push_back(t);
DSU::vis[t]=1;
DSU::sz[t]=1;
DSU::f[t]=t;
}
for(int i=0;i<k;i++)
{
int x=S[i];
for(int j=G2::head[x];j;j=G2::nxt[j])
{
int y=G2::ver[j];
LL w=G2::w[j];
if(DSU::vis[y])
{
E.push_back(Edge(x,y,w));
}
}
}
cout<<MST(S,E)<<endl;
for(int i=0;i<k;i++)
{
DSU::vis[S[i]]=0;
}
}
}
return 0;
}
|