本文共 2501 字，大约阅读时间需要 8 分钟。

题意

猫被困在围栏里，问最少去掉多长的边，使所有猫逃出来。

AC

• 并查集 + prim
  对于每个图，求它的最大生成树，总长度减去所有的最大生成树就是需要去掉的边

using namespace std;int inf = 0x3f3f3f3f;int n, m, pre[N];double sum;bool vis[N];double dis[N];struct ac{    int v;    double c;};vector
 a(N);vector
    
      g[N];void init() {    for (int i = 1; i 
     
       MAX) {                MAX = dis[j];                u = j;            }        }        if (u == -1)    return;        vis[u] = true;        sum += MAX;        for (int j = 0; j < g[u].size(); ++j) {            ac t = g[u][j];            if (vis[t.v])   continue;            if (dis[t.v] < t.c ) {                dis[t.v] = t.c;            }        }    }}int main(){// #ifndef ONLINE_JUDGE//     freopen("in.txt", "r", stdin);// #endif    ios::sync_with_stdio(false);    while (cin >> n >> m) {        init();        for (int i = 1; i <= n; ++i) {            cin >> a[i].first >> a[i].second;        }        double ans = 0;        for (int i = 0; i < m; ++i) {            int u, v;            cin >> u >> v;            int dx = a[u].first - a[v].first;            int dy = a[u].second - a[v].second;            double temp = sqrt(dx * dx + dy * dy);            ans += temp;            // 建图            g[u].push_back((ac){v, temp});            g[v].push_back((ac){u, temp});            join(u, v);        }        for (int i = 1; i <= n; ++i) {            // 求这个并查集的最大生成树            if (pre[i] == i) {                sum = 0;                prim(i);                ans -= sum;            }        }        printf("%.3lf\n",ans);        for (int i = 1; i <= n; ++i) {            g[i].clear();        }    }    return 0;}
     
    

• 贪心
  对所有边降序排列，如果两个边不连通，就减去这条边，剩下的就是需要去掉的边

using namespace std;int inf = 0x3f3f3f3f;int n, m, pre[N];struct ac{    int u, v;    double c;    bool operator < (const ac &x)const {        return c > x.c;    }};vector
 a(N);vector
    
      g;void init() {    for (int i = 1; i 
     
      > n >> m) {        init();        for (int i = 1; i <= n; ++i) {            cin >> a[i].first >> a[i].second;        }        double ans = 0;        for (int i = 0; i < m; ++i) {            int u, v;            cin >> u >> v;            int dx = a[u].first - a[v].first;            int dy = a[u].second - a[v].second;            double temp = sqrt(dx * dx + dy * dy);            ans += temp;            g.push_back((ac){u, v, temp});        }        sort(g.begin(), g.end());        ans -= rm();        printf("%.3lf\n",ans);        g.clear();    }    return 0;}
     
    

转载地址：http://ckprf.baihongyu.com/