[Poi2012]Tour de Byteotia

题目链接：

---

题解：

这类题有一个套路，就是他不要求的点可以随便搞。

我们只需要保证前$k$个点是对的就行。

因此，如果一条边的有至少一个是关键点的端点，我们设当前边是关键边。

有结论：只删关键边一定是最优的。

然后枚举就行了。

代码：

#include 
     
      #define N 1000010 using namespace std;char *p1, *p2, buf[100000];#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )int rd() {    int x = 0, f = 1;    char c = nc();    while (c < 48) {        if (c == '-')            f = -1;        c = nc();    }    while (c > 47) {        x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();    }    return x * f;}int fa[N];struct Node {    int x, y;}e[N << 1];int find(int x) {    return fa[x] == x ? x : fa[x] = find(fa[x]);}int main() {    int n = rd(), m = rd(), k = rd();    for (int i = 1; i <= n; i ++ ) {        fa[i] = i;    }    for (int i = 1; i <= m; i ++ ) {        e[i].x = rd(), e[i].y = rd();        if (e[i].x > k && e[i].y > k) {            int x = find(e[i].x), y = find(e[i].y);            if (x != y) {                fa[x] = y;            }        }    }    int ans = 0;    for (int i = 1; i <= m; i ++ ) {        if (e[i].x <= k || e[i].y <= k) {            int x = find(e[i].x), y = find(e[i].y);            if (x != y) {                fa[x] = y;            }            else {                ans ++ ;            }        }    }    cout << ans << endl ;    return 0;}
     

小结：由于题目把一些点设为了关键点，那么我们就把边分为带关键点的和不带关键点的就好。