M_sea

洛谷1041 传染病控制
Luogu分析将树分层,那么每次病毒会下移一层。考虑贪心,每次砍掉节点最多的一条边。但是这样的做法是不行的,(反例...
扫描右侧二维码阅读全文
05
2018/10

洛谷1041 传染病控制

Luogu

分析

将树分层,那么每次病毒会下移一层。

考虑贪心,每次砍掉节点最多的一条边。

但是这样的做法是不行的,(反例随便举)

所以考虑Dfs每一层断掉哪条边。断掉一条边后就等于保护了该子树。于是再用一个Dfs标记子树中所有节点,这些节点不能再被断掉。

每次Dfs开头就更新一下答案。因为不一定能搜到底。

细节非常多。具体见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int min_(int a,int b) { return a<b?a:b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; } e[610];
int head[310],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int n,m,dep=0;
int level[310];
int sz[310],fa[310];
bool vis[310];
vector<int> p[310]; //维护每一层的节点

inline void Dfs1(int u) { //分层+求子树大小+求最大深度
    sz[u]=1; vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa[u]) continue;
        level[v]=level[u]+1;
        p[level[v]].push_back(v);
        dep=max(dep,level[v]);
        fa[v]=u;
        Dfs1(v); sz[u]+=sz[v];
    }
}

int ans=2147483647;
bool tag[310];

inline void _(int u,int t) { //标记子树
    tag[u]=t;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa[u]) continue;
        _(v,t);
    }
}

inline void Dfs2(int l,int now) { //搜索答案
    ans=min_(ans,now);
    if (l>dep) return;
    int tmp=p[l].size();
    for (re int i=0;i<tmp;i++) {
        int u=p[l][i];
        if (tag[u]) continue;
        now-=sz[u]; _(u,1);
        Dfs2(l+1,now);
        now+=sz[u]; _(u,0);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1,u,v;i<=m;i++) {
        u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    level[1]=0; p[0].push_back(1); Dfs1(1);
    Dfs2(1,n); printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 29 PM

发表评论