一个很不错的题? 反正我是做得非常蛋疼。

似乎算法和解法都不是很难, 但是性质观察起来有一点困难。

其实最恶心的是, 看出一个性质, 以为是一种特殊情况不敢做。

传送门

题目大意

给你一个\(n\)个点\(m\)条边的无向图,每条边有权值,我们可以选择一个整数lim来生成一个新的图,过程如下:

  1. 先将原图中边权小于lim的边删掉
  2. 依次从1到n枚举每个点
  3. 如果这个点没有边于它相连,这个点将会被删去
  4. 如果这个点只与两条不相同的边x,y相连,设这两条边的另一个点分别为a,b,如果a,b和这个点都不相同(a,b可以相同),则依次做如下操作:
    1. 删去边x,y
    2. 删去这个点
    3. 在a,b之间建立一条新的边

解题报告

考虑离线, 依次把边权从大到小执行操作。

几个性质:

  1. 被删除的点只会是度数为0, 2的点。
  2. 度数为2的点, 如果是一个环内的最后一个点, 那么不会被删除。
  3. 删除一个点, 不会改变其他点的度数。

然后就需要记录度数为\(0\)的点的个数\(S_0\), 度数为\(2\)的点的个数\(S_2\), 和环的个数\(S_{cycle}\).

然后就可以得到剩余的点和边的个数。

代码

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
const int N=300100;
int s0, s2, sc;
int f[N],du[N],tw[N],sz[N];
int n,m,q;
int a[N],b[N],c[N],k[N];
int od[N],oq[N],as1[N],as2[N];
inline void in(int &x) {
char c=getchar(); int f=1;
for (;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:f);
for (x=0; c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
x*=f;
}
inline bool cmpd(int x, int y) { return c[x]>c[y]; }
inline bool cmpq(int x, int y) { return k[x]>k[y]; }
int find(int x) { return (f[x]==x?x:(f[x]=find(f[x]))); }
inline void come(int id) {
int x(a[id]), y(b[id]), v(c[id]);
int fx=find(x), fy=find(y);
if (tw[fx]==sz[fx]) --sc;
if (fy!=fx&&tw[fy]==sz[fy]) --sc;
if (du[x]==0) --s0; if (du[y]==0) --s0;
if (du[x]==1) ++s2,++tw[fx]; if (du[y]==1) ++s2,++tw[fy];
if (du[x]==2) --s2,--tw[fx]; if (du[y]==2) --s2,--tw[fy];
++du[x], ++du[y];
if (fx!=fy) f[fx]=fy, sz[fy]+=sz[fx], tw[fy]+=tw[fx];
if (tw[fy]==sz[fy]) ++sc;
}
int main() {
in(n),in(m);
rep(i,1,m) in(a[i]),in(b[i]),in(c[i]),od[i]=i;
in(q); rep(i,1,q) in(k[i]),oq[i]=i;
sort(od+1,od+1+m, cmpd);
sort(oq+1,oq+1+q, cmpq);
rep(i,1,n) f[i]=i,du[i]=0,tw[i]=0,sz[i]=1;
s0=n, s2=0, sc=0;
int i=1, j=1;
for (; i<=q; ++i) {
while (j<=m&&c[od[j]]>=k[oq[i]])
come(od[j]), ++j;
as1[oq[i]]=n-s0-s2+sc;
as2[oq[i]]=j-1-s2+sc;
}
rep(i,1,q) printf("%d %d\n", as1[i],as2[i]);
return 0;
}

留言