Description

给定一个n个点m条边的无向图，问最少删掉多少条边能使得编号小于等于k的点都不在环上。

Analysis

包含关键点的环中

包含从关键点连出的两条边

考虑我们删边删哪些边更优

根据贪心

我们会删与关键点相连的边

一直删我们发现不会删掉不与关键点相连的边

Solution

于是我们先把边顶点都大于k的先连起来

相当于合并了一些点

在新的图里，每个连通块里都不能生成环

那最多保留一棵生成树

Solution

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cctype>

#include <cmath>

using namespace std;

const int M=1000007;

inline int rd(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-')  f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int n,m,k;

int f[M],hav[M];

struct node{

    int x,y;

    node(int xx=0,int yy=0){x=xx;y=yy;}

}ed[M<<1];

int te;

int find(int x){

    return (f[x]==x)?x:(f[x]=find(f[x]));

}

int link(int x,int y){

    x=find(x);y=find(y);

    if(x!=y){

        f[x]=y;

        hav[y]=hav[x]|hav[y];

        return 0;

    }

    return hav[x];

}

int main(){

    int i,x,y,ans=0;

    n=rd(),m=rd(),k=rd();

    for(i=1;i<=n;i++) f[i]=i;

    for(i=1;i<=k;i++) hav[i]=1;

    for(i=1;i<=m;i++){

        x=rd(),y=rd();

        if(x>k&&y>k){

            link(x,y);

        }

        else ed[++te]=node(x,y);

    }

    for(i=1;i<=te;i++)

        ans+=link(ed[i].x,ed[i].y);

    printf("%d\n",ans);

    return 0;

}

巴特西

bzoj 3060[Poi2012]Tour de Byteotia 贪心+生成树

Description

Analysis

Solution

Solution

最新文章

热门文章