题目传送门

Description

我们称一张无向图是仙人掌,当且仅当这张无向图连通且每条边最多属于一个简单环。我们称一张无向图是沙漠,当且仅当这张无向图中所有连通子图都是仙人掌。

给出一个 $n$ 个点,$m$ 条边的沙漠,你可以删去其中的 $k$ 条边。求能分成的连通块数量最大值。

Solution

很容易想到,对于每条链,删一条边,多一个连通块。对于每个环,需要先破环为链。

找出每个环,贪心即可。

Code

/*
 * @Name: B
 * @Author: Lovely_XianShen
 * @Date: 2019-10-31 18:17:01
 * @Aqours!Sunshine!!
 */
 #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

const int N = 4e6 + 5, M = 4e6 + 5;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

#define int long long

int n, m, k;

int huancnt;
int huan[N],dis[N];

bool vis[N];

int s[N], top = 0;

int sum = 0;

int head[N], tot;

struct edg {
    int nxt, to;
} e[M ];

inline void add(int x, int y) {
    e[++tot].to = y;
    e[tot].nxt = head[x];
    head[x] = tot;
}

int dfn[N], low[N];
int timer;

bool in[N];

void dfs(int x, int fa) {
    vis[x]=1;
//    cout<<"dfsing"<<x<<endl; 
    dfn[x] = low[x] = ++timer;
    s[++top] = x;
    for (int i = head[x]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (to == fa)
            continue;
    //    cout<<"x"<<x<<" to"<<to<<endl;
        if (!dfn[to]) {
    //        cout<<"dfn"<<to<<"为0"<<endl; 
            dfs(to, x);
            low[x] = min(low[x], low[to]);
        } else
            low[x] = min(low[x], dfn[to]);
    }
    int tmp = 0;
    if (low[x] == dfn[x]) {
        sum++;
    //    cout<<"在"<<x<<"的位置发现环"<<endl; 
        while (1) {
            int now = s[top];
            top--;
            
            in[now] = 1;
            if (x == now)
                break;
        }
//        if (tmp > 1) {
//            sum += tmp;
//        }
    }
}

bool cmp(int x, int y) {
    return x > y;
}

void dfs2(int x,int fa){
//    cout<<"dfsing"<<x<<endl; 
    for(int i=head[x];i;i=e[i].nxt){
        int to=e[i].to;
        if(to==fa) continue;
        if(dis[to]==0){
//        cout<<to<<endl; 
            dis[to]=dis[x]+1;
            dfs2(to,x);
        }
        else if(dis[to]<dis[x]+1)
            huan[++huancnt]=dis[x]-dis[to]+1; 
    }
}

signed main() {
    int newSCC=0;
    n = read();
    m = read();
    k = read();
    for (int i = 1; i <= m; i++) {
        int x, y;
        x = read();
        y = read();
        add(x, y);
        add(y, x);
    }
    //cout<<"qaq"<<endl;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            dfs(i, 0);
            newSCC++;
        }// cout << "qaq" << endl;
    }
   // cerr << "sum="<<sum << endl;
    newSCC=sum-newSCC;
    //cout<<newSCC<<k<<endl;
    if (newSCC >= k) {
        cout << sum + k-newSCC << endl;
        return 0;
    }
    k -= newSCC;
    
    for(int i=1;i<=n;i++){
        if(dis[i]==0) 
        dis[i]=1,dfs2(i,0);
    }
    sort(huan + 1, huan + 1 + huancnt, cmp);
    int ans=sum;
    for (int i = 1; i <= huancnt; i++) {
     //   cout<<"这个环大小为"<<huan[i]<<endl;
     //   cout<<"k大小"<<k<<endl;
     //   cout<<"anscnt"<<anscnt<<endl;
        k--;
    
        ans+=min(k,huan[i]-1);
        k-=huan[i]-1;
        if(k<=0) break;
    }
    cout<<ans<<endl;
    return 0;
}