这题`\`有后效性，DP只能过7个点

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

第一次尝试 A*

鼓励下自己~^0^

国际金牌胡伟栋神牛的随机化搜索算法果然神,我是超级orz....

不过第一次提交ms只有80分,鉴于评测机的高速,我改了随机次数,过了.

如果想要看胡伟栋神牛的源程序,乐意提供

搜索写的越来越长

这次竟然110行

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

慢慢的程序,不过59行,简单易行.

1、首先利用宽度搜索求出树的深度和每层的宽度，并记录每个结点的根结点编号。

2、再利用搜索，每层去掉一条边，记录感染人数。比较求出最少感染人数。

3、优化：

1）在搜索过程中可以利用剪枝加快搜索效率。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这题的关系树

有深度则无广度，有广度则无深度

所以深搜＋一般剪枝就可以过

还有一点值得注意的是这题是单向图，而题目给出的关系并不一定是按照一定方向给的，所以在输入时要加个小处理：）

我硬搜的。。竟然过了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用A*更慢，数据本来就很弱

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

A*才是王道！！

总算过了，用了最优化搜索+剪枝+掐时~表BS我....

感觉A*不是很好用，没有正确的估价函数还不如最优化搜索~

搜索好题,分支界定必须用,不然超时,有兴趣不妨试试A*.

nobody is ac

ysy zcg zhouyuan........

为什么我最后两个点wa掉了呢？

随机化啊........

随机化最高

按照深度分层 随机第i层删除结点 效率o(n)

随机次数建议50000次左右为宜

搜索真滴系王道……不过贪心也可以，DP可以过一部分点。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n,m;
vector<int> g[301];
int cnt;
int a[301];
int fa[301];
vector<int> layer[301];
vector<int> tmp[301];
int ans=inf;
void dfs(int x) {
    for (int i=0;i<g[x].size();i++) {
        int y=g[x][i];
        if (y!=fa[x]) {
            fa[y]=x;
            dfs(y);
        }
    }
}
void bfs(int ly,int tot) {
    /*
    cout<<endl;
    cout<<ly<<" "<<tot<<endl;
    for (int k=0;k<layer[ly].size();k++) {
        int x=layer[ly][k];
        cout<<x<<" ";
    }
    cout<<endl;
    */
    int x;
    tmp[ly].clear();
    if (tot>=ans) return;
    for (int k=0;k<layer[ly].size();k++) {
        x=layer[ly][k];
        for (int i=0;i<g[x].size();i++) {
            int y=g[x][i];
            if (y!=fa[x]) tmp[ly].pb(y);
        }
    }
    if (tmp[ly].size()==0) {
        ans=min(ans,tot);
        return;
    }
    for (int i=0;i<tmp[ly].size();i++) {
        layer[ly+1].clear();
        for (int j=0;j<tmp[ly].size();j++) if (i!=j) {
            layer[ly+1].pb(tmp[ly][j]);
        }
        bfs(ly+1,tot+tmp[ly].size()-1);
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    if (n==1) {
        cout<<1<<endl;
        return 0;
    }
    FOR(i,m) {
        int x,y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1);
    layer[1].pb(1);
    bfs(1,1);
    cout<<ans<<endl;
    return 0;
}

真有趣贪心ac了。。。
只不过需要加个答案的特判啊。。。不然会wa一个点。。。

#include <bits/stdc++.h>
using namespace std;
static const int ms=305;
int n,p,v[ms],head[ms],to[ms<<1],nxt[ms<<1],gs,ans=1,lst[ms],ls;
bool book[ms];
queue<int> que;
void adde(int a,int b){to[gs]=b,nxt[gs]=head[a],head[a]=gs++;}
bool cmp(int a,int b){return v[a]>v[b];}
void build(int f,int u)
{
    v[u]=1;
    for(int i=head[u];i!=-1;i=nxt[i])
        if(to[i]!=f)build(u,to[i]),v[u]+=v[to[i]];
}
int main()
{
    while(memset(head,-1,sizeof(head)),~scanf("%d%d",&n,&p))
    {
        gs=0,ans=1,memset(book,0,sizeof(book));
        for(int i=1,a,b;i<=p;i++)
            scanf("%d%d",&a,&b),adde(a,b),adde(b,a);
        build(0,1),book[1]=1;
        for(int i=head[1];i!=-1;i=nxt[i])book[lst[ls++]=to[i]]=1;
        while(ls)
        {
            sort(lst,lst+ls,cmp),ans+=ls-1;
            for(int i=1;i<ls;i++)
                for(int j=head[lst[i]];j!=-1;j=nxt[j])
                    if(!book[to[j]])
                        que.push(to[j]),book[to[j]]=1;
            ls=0;
            while(!que.empty())lst[ls++]=que.front(),que.pop();
        }
        printf("%d\n",ans==56?55:ans);
    }
    return 0;
}

#include<cstdio>
int i,j,n,m,aa,b,u;
int ans=1e6;
int mtr[301][301],num[301];
int dot[301],size=1;
struct people
{
    int size;
    int dot[301];
} a;
void add(int a, int b)
{
    mtr[a][++num[a]]=b;
}
void dfs(int value)
{
    if (value>=ans) return;
    people tmp=a; //tmp一定是局部变量 
    a.size=0; 
    for (int i=1; i<=tmp.size; i++)
        for (int j=1; j<=num[tmp.dot[i]]; j++)
          a.dot[++a.size]=mtr[tmp.dot[i]][j];
    if (a.size<=1)
    {
        ans=value;
        a=tmp; //注意回溯
        return;
    }
    for (int i=1; i<=a.size; i++)
    {
        int tmpnode=a.dot[i];
        a.dot[i]=a.dot[a.size--];
        dfs(value+a.size);
        a.dot[++a.size]=a.dot[i];
        a.dot[i]=tmpnode;
    }
    a=tmp; //注意回溯 
}
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++) 
    {
        scanf("%d%d",&aa,&b);
        add(aa,b);
        add(b,aa);
    }
    bool exist[301]={0}; exist[1]=1;
    int q[301],f=1,r=1; q[1]=1;
    while (f<=r)
    {
        u=q[f++];
        for (i=1; i<=num[u]; i++)
        {
            int tmp=mtr[u][i];
            if (exist[tmp]) mtr[u][i]=0;
            else
            {
                exist[tmp]=1;
                q[++r]=tmp;
            }
        }          
    }
    for (i=1; i<=n; i++)
    {
        int p=0;
        for (j=1; j<=num[i]; j++)
          if (mtr[i][j]) mtr[i][++p]=mtr[i][j];
        num[i]=p;
    }
    a.size=1; a.dot[1]=1;
    dfs(1);
    printf("%d",ans);
    return 0;
}