题解

107 条题解

  • 13
    @ 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;
    }
         
    
  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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

      例如,两个儿子一个单链非常大,一个儿子下一层分支非常多,此时先减小的会更优,而你只在个数相等时选择减分支多的

    • @ 2017-10-16 08:22:52

      @魂混浑: 吕布搞得好

  • 0
    @ 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
    @ 2016-08-21 21:23:00

    说的是给定一棵树,结果输入的都是无向边,为此WA了两次。
    首先dfs把无向图转有向图,然后再搜索。
    搜索非常裸,每次枚举砍掉A里面的哪个点,然后把剩下的点能到达的所有点存进B里面,再dfsB。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;

    const int INF = 1000000000;
    const int maxn = 300 + 10;

    int n, m;
    int acc[maxn][maxn];
    vector<int> G[maxn];

    void dfs (int u, int f) {
    for (int v = 0; v < n; v++) if (acc[u][v] && v != f) {
    G[u].push_back(v);
    dfs(v, u);
    }
    }

    int dfs (const vector<int>& A) {
    int l = A.size();
    if (!l) return 0;
    int ans = INF;
    vector<int> B;
    for (int i = 0; i < l; i++) { //cut i
    B.clear();
    for (int j = 0; j < l; j++) if (j != i) {
    int u = A[j];
    for (int k = 0; k < G[u].size(); k++) B.push_back(G[u][k]);
    }
    ans = min(ans, dfs(B));
    }
    return ans + l - 1;
    }

    int main () {
    cin >> n >> m;

    while (m--) {
    int u, v;
    cin >> u >> v; u--; v--;
    acc[u][v] = acc[v][u] = 1;
    }

    dfs(0, -1);

    vector<int> A;
    for (int i = 0; i < G[0].size(); i++)
    A.push_back(G[0][i]);

    cout << dfs(A)+1;
    return 0;
    }
    ```

  • 0
    @ 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
    @ 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
    @ 2009-10-30 07:44:13

    p有什么用?

  • 0
    @ 2009-10-29 20:21:33

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

    无语....

  • 0
    @ 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
    @ 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
    @ 2009-10-27 15:05:43

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

  • 0
    @ 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排。。。

信息

ID
1101
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2888
已通过
781
通过率
27%
上传者