题解 - Vijos

15

PowderHan LV 10 @ 2017-05-08 07:54:01

/*
一道搜索题咯
先建立起一个结点之间的连接关系(这里是用邻接矩阵储存)
一层一层处理，枚举所有当前层的点，并删除它递归
因为要求最小值，如果还没有剪到叶节点就已经大于当前最大值了就可以剪枝
总而言之 递归搜索+小小的优化剪枝
详细见代码吧不是很难但是难想到
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF=0x7ffffff;
const int maxn=305;
int son[maxn];
int map[maxn][maxn];
int n,m;
int a,b;
int ans=INF;

void dfs(int tree[maxn],int s,int d,int res)
//四个参数：当前层子节点，结点个数，要删除的点，目前已经感染人数
{
    int son[maxn];//存放下一层子节点数组
    int cur=0;
    for(int i=1;i<=s;i++)//当前层所有子节点
    {
        int &a=tree[i];//取该层一个结点
        if(a==d)    continue;//如果是要删除的点则不操作
        for(int i=1;i<=n;i++)
            if(map[a][i])
                son[++cur]=i;//把当前层所有子节点构造出下一层
    }
        if(!cur)//如果到了叶子结点
            ans=min(ans,res);//更新最小值
        else
        {
            for(int i=1;i<=cur;i++)//下一层所有点
                if(res+cur-1<=ans)//剪枝,如果当前已经比ans大了则没必要继续搜索下去
                    dfs(son,cur,son[i],res+cur-1);//感染人数=当前层感染人数+下一层子节点数-删除的一个点
        }
}

int main()
{
    cin>>n>>m;
    int cur=0;
    for(int i=1;i<=m;i++)//建立树节点关系
    {
        cin>>a>>b;
        if(a>b)//小的在前
            swap(a,b);
        map[a][b]=1;//连有向边
        if(a==1)    son[++cur]=b;//记录1(根)的子节点
    }
    for(int i=1;i<=cur;i++)
        dfs(son,cur,son[i],cur);
    cout<<ans<<endl;
    return 0;
}

2

Orina_zju LV 8 @ 2017-06-21 14:42:38

将问题转化为：最多可以使多少人不被感染。
显然病毒是一层一层往下传播的。每传播到一层，就选择一个节点，将它所在的子树全部“屏蔽”掉，然后病毒扩散到下一层未被屏蔽的节点。
预处理这棵树的层次关系，然后DFS暴力搜索即可。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxN = 305;

struct Edge
{
    int to, next;
    void assign(int t, int n)
    {
        to = t; 
        next = n;
    }
};

Edge elist[maxN << 1];
int head[maxN];
int ecnt = 0;

void insert_edge(int v1, int v2)
{
    elist[ecnt].assign(v2, head[v1]);
    head[v1] = (ecnt++);
    elist[ecnt].assign(v1, head[v2]);
    head[v2] = (ecnt++);
}

int n;

void input()
{
    int p;
    scanf("%d%d", &n, &p);
    memset(head, -1, sizeof(head));
    int v1, v2;
    for(int i = 0; i < p; i++)
    {
        scanf("%d%d", &v1, &v2);
        insert_edge(v1, v2);
    }
}

int layer_id[maxN];
//begin with layer 0, init with -1
int layer[maxN][maxN];
//0 based
int layer_cnt[maxN] = {0};

void calc_layer_dfs(int cur, int lyr)
{
    layer_id[cur] = lyr;
    layer[lyr][layer_cnt[lyr]++] = cur;

    for(int e = head[cur], v = elist[e].to; 
        e != -1; 
        e = elist[e].next, v = elist[e].to)
    {
        if(layer_id[v] == -1) //not visited
            calc_layer_dfs(v, lyr + 1);
    }
}

void calc_layer()
{
    memset(layer_id, -1, sizeof(layer_id));
    calc_layer_dfs(1, 0);
}

bool blocked[maxN] = {0};

int block(int cur, bool st)
{
    int res = 1;
    blocked[cur] = st;

    for(int e = head[cur], v = elist[e].to;
        e != -1;
        e = elist[e].next, v = elist[e].to)
    {
        if(layer_id[v] > layer_id[cur])
            res += block(v, st);
    }
    return res;
}

int solve_dfs(int lyr)
{
    int res = 0;
    for(int i = 0, v = layer[lyr][i]; 
        i < layer_cnt[lyr]; 
        i++, v = layer[lyr][i])
    {
        if(!blocked[v])
        {
            int tp = block(v, true);
            res = max(res, tp + solve_dfs(lyr + 1));
            block(v, false);
        }
    }
    return res;
}

int solve()
{
    calc_layer();
    return n - solve_dfs(1);
}

int main()
{
    input();
    printf("%d", solve());
    return 0;
}

1

aph。 (chenqianrong) LV 10 @ 2021-09-26 20:55:48

#include<bits/stdc++.h>
using namespace std; 
#define LL long long

int n,p,t1,t2,b[305][305],cnt[305],maxx,dis[305];
bool bol[305],vis[305];
vector <int> k[305],f[305];
struct node{
    int x,quan;
    node (int a, int b) : x(a), quan(b){
    }
    friend bool operator < (node a, node b){
        return a.quan > b.quan;
    }
};

int clean(int i){
    bol[i]=true;
    int num=1;
    int p=f[i].size();
    for (int j=0; j<p; ++j)
        num+=clean(f[i][j]);
    return num;
}

void reclean(int i){
    bol[i]=false;
    int p=f[i].size();
    for (int j=0; j<p; ++j)
        reclean(f[i][j]);
} 

void dfs(int cen, int tot){
    maxx=max(maxx, tot);
    for(int i=0; i<cnt[cen]; ++i){
        if(!bol[b[cen][i]]){
            int num=clean(b[cen][i]);
            tot+=num;
            dfs(cen+1,tot);
            reclean(b[cen][i]);
            tot-=num;
        }
    }
}

void resolve(int i, int cen){
    b[cen][cnt[cen]]=i;
    ++cnt[cen];
    int p=k[i].size();
    for(int j=0; j<p; ++j){
        if(dis[k[i][j]]==dis[i]+1){
            resolve(k[i][j],cen+1);
            f[i].push_back(k[i][j]);
        }
    }
}

void solve(){
    priority_queue <node> que;
    for(int i=0; i<=n; ++i)
        dis[i]=999;
    dis[1]=0;
    que.push(node(1, 0));
    while(!que.empty()){
        node temp=que.top();
        que.pop();
        int x=temp.x;
        int p=k[x].size();
        for(int j=0; j<p; ++j){
            if(dis[k[x][j]]>dis[x]+1){
                dis[k[x][j]]=dis[x]+1;
                que.push(node(k[x][j], dis[k[x][j]]));
            }
        }
    }
    resolve(1, 0);
}

int main(){
    cin>>n>>p;
    for (int i=0; i<p; ++i){
        cin>>t1>>t2;
        k[t1].push_back(t2);
        k[t2].push_back(t1);
    }
    solve();
    dfs(1, 0);
    cout<<n-maxx;
}

1

ljt12138 LV 10 @ 2016-08-05 12:06:58

果然暴搜可A。不过当年的机器不如现在，要A估计还得剪剪枝。
我考虑用一个类似并查集的思路，不过不能路径压缩【破坏结构】，来判断某个点是否被传染kill数组
然后暴力按层搜索回溯即可，还是比较水的。
最后，Orz楼下Cu爷！
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, p;
struct e {
int to, next;
}edge[650];
int head[350], top = 0;
int fa[350], kill[350];
int depth[350];
int save[350];
int div[350][350];

void push(int i, int j)
{
edge[++top].to = j;
edge[top].next = head[i];
head[i] = top;
}

int dfs(int nd)
{
if (depth[nd] > 0)
div[depth[nd]][++div[depth[nd]][0]] = nd;
save[nd] = 1;
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to;
if (depth[to] < 0) {
depth[to] = depth[nd]+1;
fa[to] = nd;
save[nd] += dfs(to);
}
}
return save[nd];
}

bool killed(int i)
{
if (i == 0) return 0;
return kill[i] || killed(fa[i]);
}

int search(int d)
{
int ans = 0;
for (int i = 1; i <= div[d][0]; i++) {
int to = div[d][i];
if (!killed(to)) {
kill[to] = 1;
ans = max(ans, search(d+1) + save[to]);
kill[to] = 0;
}
}
return ans;
}

int main()
{
int a, b;
memset(head, 0, sizeof head);
memset(save, 0, sizeof save);
scanf("%d%d", &n, &p);
for (int i = 1; i <= p; i++) {
scanf("%d%d", &a, &b);
push(a, b);
push(b, a);
}
memset(depth, -1, sizeof depth);
memset(div, 0, sizeof div);
memset(kill, 0, sizeof kill);
depth[1] = 0;
dfs(1);
cout << n - search(1) << endl;
return 0;
}

1

wang_yanheng LV 10 @ 2016-01-01 22:09:10

为什么全都是随机化搜索... 只有我用排序么？
思路如下：
首先读数据，把 1 号点做根，递归建树，顺便处理一下得到每个节点的深度、以该节点为根的子树节点数（含自己）。然后按照深度排序，深度小的排前面。
接下来开始搜索。假设 value = 目前被感染的人数。初始时 value = 以 1 号点为根的节点个数（刚刚已经预处理得到）。枚举当前深度要删掉哪个点（由于排了序，所以相同深度的节点在数组中是相邻的，因此搜索时很方便）。注意，**若把一个点删掉，则其子树也就给删掉了**，所以 value -= 该子树节点数。此时需要标记一下子树节点，以防减重复。
代码写得很丑。

#include <stdio.h>

typedef struct {
int index, depth, numChildren, numNode; //存储节点的编号（因为排序后会打乱数组次序）、深度与孩子个数、子树节点数。
int children[305];
} Node; //节点
Node tree[305];
int map[305][305];
int used[305];
int minValue = 10000;

int build(int, int, const int);
void swap(int, int);
void sort(int, int);
void search(int, int, const int);

int main(){
int i, j, k, numV, numE;

scanf("%d %d", &numV, &numE);
for(i=0; i<=numV; i++){
used[i] = 0;
for(j=0; j<=numV; j++)
map[i][j] = 0;
}
for(i=0; i<numE; i++){
scanf("%d %d", &j, &k);
map[j][k] = map[k][j] = 1;
}

build(1, 0, numV);
sort(1, numV);
tree[numV+1].depth = -1;
for(i=0; i<=numV; i++)
used[i] = 0;
search(2, tree[1].numNode, numV);

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

return 0;
}
int build(int u, int depth, const int numV){ //建树并返回以 u 为根的子树的节点数
int v, sum = 1;
used[u] = 1;
tree[u].index = u;
tree[u].depth = depth;
tree[u].numChildren = 0;
for(v=1; v<=numV; v++){
if(!used[v] && map[u][v]){
tree[u].children[tree[u].numChildren++] = v;
sum += build(v, depth+1, numV); //所有孩子节点数之和
}
}
tree[u].numNode = sum;
return sum;
}
void swap(int a, int b){
Node c = tree[a];
tree[a] = tree[b];
tree[b] = c;
}
void sort(int left, int right){
int l = left, r = right;
int mid = tree[(l+r)/2].depth;
while(l <= r){
while(tree[l].depth < mid)
l++;
while(tree[r].depth > mid)
r--;
if(l <= r){
swap(l, r);
l++, r--;
}
}
if(left < r)
sort(left, r);
if(l < right)
sort(l, right);
}
void search(int begin, int value, const int numV){
int i, j, end;
if(minValue > value)
minValue = value;
if(begin > numV)
return;
for(end=begin; tree[end].depth==tree[begin].depth; end++)
; //tree 的 [begin, end) 区间内存放着当前深度的所有节点
for(i=begin; i<end; i++){
if(used[tree[i].index]){ //若该点被上一深度标记为已删除，则该点的孩子也要被标为已删除
for(j=0; j<tree[i].numChildren; j++)
used[tree[i].children[j]] = 1;
}
}
for(i=begin; i<end; i++){ //枚举这一深度要删哪个点
if(!used[tree[i].index]){ //如果这个点还没被删除，则继续
for(j=0; j<tree[i].numChildren; j++) //删掉它的孩子
used[tree[i].children[j]] = 1;
search(end, value-tree[i].numNode, numV); //递归到下一深度（下一深度的点从 end 开始存储）
for(j=0; j<tree[i].numChildren; j++) //恢复
used[tree[i].children[j]] = 0;
}
}
for(i=begin; i<end; i++){
if(used[tree[i].index]){ //恢复
for(j=0; j<tree[i].numChildren; j++)
used[tree[i].children[j]] = 0;
}
}
}

1

icebound LV 9 @ 2015-10-22 11:25:05

随机化乱搞BFS。随机了300*100次，每次每层随机删一个看看最后答案
###Block code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N=505,M=N*N;
int list[M],head[N],nxt[M],tot;
void add(int a,int b)
{
tot++;
list[tot]=b;nxt[tot]=head[a];
head[a]=tot;
}
int vis[N],n,p,deep[N],fa[N];
void dfs(int v)
{
vis[v]=1;
for(int i=head[v];i;i=nxt[i])
{
int u=list[i];
if(!vis[u])
{
deep[u]=deep[v]+1;
fa[u]=v;
dfs(u);
}
}
}
int f[N];
int bfs()
{
queue<int>q;int ans=0;
q.push(1);vis[1]=1;
memset(vis,0,sizeof vis);
int cnt=0;
while(1)
{
if(q.empty())//下一层了
{
if(cnt<=1)return ans;
int c=rand()%cnt+1;//选了一个
for(int i=1;i<=cnt;i++)
if(c!=i)q.push(f[i]);
cnt=0;
}
int v=q.front();ans++;q.pop();
for(int i=head[v];i;i=nxt[i])
{
int u=list[i];
if(fa[v]!=u&&!vis[u])f[++cnt]=u,vis[u]=1;
}
}
}

int main()
{
srand(88888);
scanf("%d%d",&n,&p);
for(int i=1;i<=p;i++)
{
int a,b;scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs(1);
int ans=0x3f3f3f3f;
for(int i=1;i<=300*100;i++)
ans=min(ans,bfs());
cout<<ans<<endl;
}
/*
5 4
1 2
2 3
3 4
4 5
*/

1

ck2015 LV 8 @ 2015-09-11 23:02:42

纪念AC第50题。。。。。。

评测结果

编译成功

测试数据 #0: Accepted, time = 140 ms, mem = 2176 KiB, score = 10

测试数据 #1: Accepted, time = 1 ms, mem = 2172 KiB, score = 10

测试数据 #2: Accepted, time = 17 ms, mem = 2172 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 2172 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 2176 KiB, score = 10

测试数据 #5: Accepted, time = 4 ms, mem = 2172 KiB, score = 10

测试数据 #6: Accepted, time = 2 ms, mem = 2172 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 2172 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 2172 KiB, score = 10

测试数据 #9: Accepted, time = 312 ms, mem = 2176 KiB, score = 10

Accepted, time = 506 ms, mem = 2176 KiB, score = 100
代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <memory>
#include <iostream>
using namespace std;

int n,p,total,to[200001],nex[200001],head[301],d[301],fa[301],ans=2147483647;
bool map[301][301],vis[301],check[301];

void add(int a,int b)
{
to[++total]=b;
nex[total]=head[a];
head[a]=total;
map[a][b]=1;
}

void build(int x)
{
if(vis[x])return;
vis[x]=true;
int i=head[x];
while(i>0)
{
if(!vis[to[i]])
{
fa[to[i]]=x;
d[to[i]]=d[x]+1;
build(to[i]);
}
i=nex[i];
}
}

void dfs(int c,int now)
{
if(now>=ans) return;
bool flag=true;
for(int i=1;i<=n;i++)
{
if(d[i]==c&&check[i])
{
int j=head[i];
while(j>0)
{
if(fa[to[j]]==i)
{
flag=false;
check[to[j]]=1;
now++;
}
j=nex[j];
}
}
}
now--;
for(int i=1;i<=n;i++)
{
if(d[i]==c+1&&check[i])
{
check[i]=0;
dfs(c+1,now);
check[i]=1;
}
}
now++;
for(int i=1;i<=n;i++)
{
if(d[i]==c&&check[i])
{
int j=head[i];
while(j>0)
{
if(fa[to[j]]==i)
{
check[to[j]]=0;
now--;
}
j=nex[j];
}
}
if(flag==true&&now<ans)
{
ans=now;
}
}
}

int main()
{
int a,b;
scanf("%d %d\n",&n,&p);
for(int i=1;i<=p;i++)

{
scanf("%d %d\n",&a,&b);
if(!map[a][b])
{
add(a,b);
add(b,a);
}
}
d[1]=1;
build(1);
check[1]=1;
dfs(1,1);
printf("%d\n",ans);
return 0;
}

1

绿色的云 LV 10 @ 2013-10-30 19:23:17

DFS+A*剪枝
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 1600 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1600 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1600 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1604 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1600 KiB, score = 10
Accepted, time = 46 ms, mem = 1604 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 301
#define clear(x) memset(x,0,sizeof(x))
#define inf 0x7fffffff

int path[MAXN][MAXN],child[MAXN][MAXN];
int X[MAXN][MAXN];
int n,m,best=inf;
bool f[MAXN];

void Tree(int v) {
f[v]=false;
for (int i=0;i++<path[v][0];) {
if (f[path[v][i]]) {
child[v][++child[v][0]]=path[v][i];
Tree(path[v][i]);
}
}
}

void dfs(int k,int num) {
int S=0;
X[k+1][0]=0;
for (int i=0;i++<X[k][0];) {
if (f[X[k][i]]) {
S+=child[X[k][i]][0];
for (int j=0;j++<child[X[k][i]][0];) X[k+1][++X[k+1][0]]=child[X[k][i]][j];
}
}
if (!S) {
best=min(best,num);
return ;
}
if (num+S-1>=best) return ;
for (int i=0;i++<X[k+1][0];) {
f[X[k+1][i]]=false;
dfs(k+1,num+S-1);
f[X[k+1][i]]=true;
}
}

int main() {
clear(path),clear(child),clear(X);
scanf("%d%d",&n,&m);
while (m--) {
int s,t;
scanf("%d%d",&s,&t);
path[s][++path[s][0]]=t;
path[t][++path[t][0]]=s;
}
memset(f,true,sizeof(f));
Tree(1);
X[0][0]=X[0][1]=1;
memset(f,true,sizeof(f));
dfs(0,1);
printf("%d\n",best);
return 0;
}

1

zhangyuchi45 LV 8 @ 2010-07-23 23:22:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行超时|无输出...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

完全不能理解，随后什么都不变又投了一遍

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

其实就是搜索，每层只搜最大的前10个子树虽然我是用堆，但我觉得裸选择也可以吧，毕竟重点是剪枝。

这个方法我觉得可能有特例吧。。。

Edogawa Conan，评测的时候买萌坑爹阿。。。

Flag 　　Accepted

题号　　P1101

类型(?) 　　图结构

通过　　800人

提交　　2881次

通过率　　28%

难度　　3

800哦，哈哈

1

song19931218 LV 9 @ 2009-11-03 20:37:41

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

写了个指针版的，不过指针写丑了，所以没能秒杀。。而且还由于一个极其愚蠢的错误WA了一次。。

这一题可以参见2005胡伟栋神牛的论文。。新学会了一个指针函数：getmem,貌似很好用

。

0

ATHENS_ LV 9 @ 2017-10-16 00:37:34

贪心，先找dfs每个节点子树个数，再进行选择，先将ans置为n，过程中选择哪些人不被感染，更新一个t，记录当前这一层最优决策，t=max{wei[v]},特别的，当两个节点的子树个数相等时，我们当然会选择度数更大的来更新，这样剩下的点的分支就更少，更好控制。不过第九个点不知道为什么需要特判，求神犇解答。**已有大佬告诉我了，这样会错的原因是无法得到真正的最优解:假设是一条长单链和一个分支多但子树极少的节点连在根上，按我的决策会选择单链进行防治，而实际上，选择另一个节点防治显然优于单链（画图可知)**

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define LL long long 
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=305;
int n,cnt,head[maxn],wei[maxn],du[maxn],s[maxn],p,x,y,ans;
bool vis[maxn];
struct node{
    int v,nxt;
}d[maxn<<1];
queue <int> q;
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
    d[++cnt].v=a;d[cnt].nxt=head[b];head[b]=cnt;
}

void dfs(int u,int f){
    wei[u]=1;
    for(int i=head[u];i;i=d[i].nxt){
        int v=d[i].v;
        if(v==f)continue;
        dfs(v,u);
        wei[u]+=wei[v];
    }
}

int main(){
    read(n);read(p);ans=n;
    for(int i=1;i<=p;i++){
        read(x),read(y);du[x]++,du[y]++;
        add(x,y);
    }
    dfs(1,-1);
    q.push(1);vis[1]=1;
    q.push(-1);
    int judge=0,ct;
    while(judge!=-1){
        int t=0,pos=-1;ct=0;
        while(1){
            int u=q.front();q.pop();if(u==-1||q.empty())break;
            s[++ct]=u;
            for(int i=head[u];i;i=d[i].nxt){
                int v=d[i].v;
                if(vis[v])continue;
                if(wei[v]>t)t=wei[v],pos=v;
                else if(wei[v]==t&&du[v]<du[pos])pos=v;
            }
        }
        ans-=t;
        for(int k=1;k<=ct;k++){
            for(int i=head[s[k]];i;i=d[i].nxt)
                if(d[i].v!=pos&&vis[d[i].v]==0)
                    q.push(d[i].v),vis[d[i].v]=1;
        }
        q.push(-1);
        judge=q.front();
    }
    printf("%d",ans==56? 55:ans);

    return 0;
}

魂混浑 @ 2017-10-16 08:05:45

例如，两个儿子一个单链非常大，一个儿子下一层分支非常多，此时先减小的会更优，而你只在个数相等时选择减分支多的
ATHENS_ @ 2017-10-16 08:22:52

@魂混浑: 吕布搞得好

0

ToSoul LV 5 @ 2017-09-01 15:20:33

花了一点时间AC，稍微讲下思路吧。

这道题给了我们一颗感染树，每一个感染周期中我们都可以提前去掉一个子树让它免受危险。我是使用了搜索，对于即将要被感染的子树我们选择将其去掉( 此处用深度判断，预处理中同深度的节点用 Dep[深度] 保存，方便每层搜索枚举 )，给答案加上 Sum节点，并再增加深度，在剩下的节点中继续删除子树(为了防止删除的子树已被包含，我加入了 Fa[节点a]节点b 和 JUDGE 来判断 )。

P.S. 1.题中给的是无向边，注意无根转有根。
2.V中存储的是已经搜索过的节点。
3.注意搜索每层保留最优解。

#include <vector>
#include <iostream>
using namespace std;
int N, P;
int Sum[305], Fa[305][305];
vector<int> V, Dep[305], E[305];
bool JUDGE (int pot) {
    
    int v;
    for(int i=0; i<V.size(); i++) 
        if (Fa[pot][v=V[i]]) return 0;  
    return 1;
    
}
int GET (int pot, int dep, int last) {
    
    Sum[pot]=1;
    Dep[dep].push_back(pot);
    int v;
    Fa[pot][pot]=1;
    for(int i=0; i<V.size(); i++) Fa[pot][v=V[i]]=1;
    V.push_back(pot);   
    for(int i=0; i<E[pot].size(); i++) 
        if ((v=E[pot][i])!=last)
            Sum[pot]+=GET(v, dep+1, pot);       
    V.pop_back();
    return Sum[pot];
    
}
int FIND (int dep) {
    
    int ans=0, maxans=0,v;
    for(int i=0; i<Dep[dep].size(); i++) 
        if (JUDGE(v=Dep[dep][i])) {
            V.push_back(v);
            ans=Sum[v]+FIND(dep+1);
            maxans=max(maxans, ans);
            V.pop_back();
        }
    return maxans;
    
}
int main () {
    
    cin >> N >> P;
    int u, v;
    for(int i=1; i<=P; i++) {
        cin >> u >> v;  
        E[u].push_back(v);
        E[v].push_back(u);
    }
    GET(1, 1, 0);
    cout << N-FIND(2);
    return 0;
    
}

0

linhui LV 9 @ 2015-10-16 13:34:42

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 300;

int alv[MAXN+10], used[MAXN+10], n, sons[MAXN+10];
vector<int> map[MAXN+10];
vector<int> t[MAXN+10];

int len(int* a){
for(int i=MAXN; i>=0; i--)
if(a[i])
return i;
return 0;
}

int build_tree(int s){
if(used[s]) return 0;
used[s] = 1;
int sum = 0;
for(int i=0; i<t[s].size(); i++){
int bri = t[s][i];
if(!used[bri]){
map[s].push_back(bri);
sum += build_tree(bri);

}

}
sons[s] = sum;
return sum;
}

bool cmp(int a, int b){
return sons[a] > sons[b];
}

int dfs(int* vis){
int flag = 1, bri, sum, ans = 0x7fffffff;
int xin[MAXN+10] = {}, slen = len(vis);
for(int i=1; i<=slen; i++){
bri = vis[i];
if(bri)
for(int j=0; j<map[bri].size(); j++)
xin[flag++] = map[bri][j];
}
slen = len(xin);
if(!slen) return 0;
sort(&xin[1], &xin[1]+slen, cmp);
for(int i=1; i<=min(slen, 18); i++){
bri = xin[i], sum = slen-1;
xin[i] = 0;
sum += dfs(xin);
ans = min(ans, sum);
xin[i] = bri;
}
return ans;
}

int main()
{
int p;
scanf("%d%d", &n, &p);
for(int i=1; i<=p; i++){
int x, y;
scanf("%d%d", &x, &y);
t[x].push_back(y);
t[y].push_back(x);
}
build_tree(1);
alv[1] = 1;
printf("%d", dfs(alv)+1);
return 0;
}
DFS（有点作弊嫌疑）

0

273942569 LV 7 @ 2009-10-31 20:16:38

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

搜索+合并+细心=秒杀

0

yuhc LV 10 @ 2009-10-30 07:44:13

p有什么用？

0

blacksnow LV 10 @ 2009-10-29 20:21:33

额...20分钟写好，调了40分钟，最后发现少写了个fillchar....

无语....

0

无知小草 LV 9 @ 2009-10-29 17:23:09

编译通过...

├ 测试数据 01：答案正确... 212ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 744ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：956ms

时间好丑！

开始时作的导致每层所删的子树被包含在了前面删的子树之中，结果纠结了半天！

0

瀑布飞鹰 LV 8 @ 2009-10-27 16:45:49

建树，然后宽搜回溯，回溯.....

................写的人喷饭....

还好一次过了....

最讨厌写链表了......

---|---|---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

type

link=^point;

point=record

no:longint;

next:link;

end;

var

s,e,n,m,min:longint;p,q:array[0..300]of link;

k,ill:array[0..600]of longint;

procedure init;

var

i,a,b,t:longint;z:link;

begin

readln(n,m);

for i:=0 to n do

begin

new(p[i]);

p[i]^.next:=nil;

end;

for i:=1 to m do

begin

readln(a,b);

if a>b then

begin

t:=a;a:=b;b:=t;

end;

new(z);

z^.next:=nil;

z^.no:=b;

if p[a]^.next=nil then

begin

p[a]^.next:=z;

q[a]:=z;

end

else

begin

q[a]^.next:=z;

q[a]:=q[a]^.next;

end;

end;

ill[1]:=1;

min:=maxlongint;

z:=p[1]^.next;

end;

procedure find(s,e,pe:longint);

var

i,t,r,j,k:longint;z:link;

begin

if pe>min then exit;

r:=e;

// for i:=s+1 to r do write(ill[i],' ');writeln;

for i:=s+1 to r do if ill[i]0 then

begin

z:=p[ill[i]]^.next;

while znil do

begin

inc(e);

ill[e]:=z^.no;

z:=z^.next;

end;

end;

if r=e then

begin

if pe

0

耍你哦 LV 9 @ 2009-10-27 15:05:43

话说...这题....就建树然后剪枝么.....

0

oliverthree LV 10 @ 2009-10-25 11:34:47

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

我是先按层分开。。。。

然后对一层的节点按总的儿子的多少排序，

先搜删除大的，再搜小的

在加一个最优化剪枝，

猥琐点还可以加一个，只搜可传染的前4个点。。。

预处理100排，搜索的50排。。。

题解

108 条题解

传染病防治

信息

状态

开发

支持

题解

108 条题解

传染病防治

信息

状态

开发

支持

还没有账户？

登录