比赛 2024暑假C班集训C 评测结果 WWWATTTTTT
题目名称 喵星人集会 最终得分 10
用户昵称 123 运行时间 11.450 s
代码语言 C++ 内存使用 3.43 MiB
提交时间 2024-07-12 11:28:57
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=55;
char s[N];
int n,g[N][N],dp[N][N],dis[N],vis[N],ret=1e9,f=0,flag[N],now[N];
int dijstra(int s,int t)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    for (int i=1;i<n;i++)
    {
        int mi=1e9,cnt=0;
        for (int j=1;j<=n;j++)
        {
            if (!vis[j] && dis[j]<mi)
            {
                mi=dis[j];
                cnt=j;
            }
        }
        vis[cnt]=1;
        for (int j=1;j<=n;j++)
        {
            if (dis[j]>dis[cnt]+1 && g[j][cnt])
            {
                dis[j]=dis[cnt]+1;
            }
        }
    }
    return dis[t];
}
void dfs(int step,int cnt)
{
    if (step==f+1)
    {
        int e=0;
        for (int i=1;i<=n;i++)
        {
            if (flag[i])
            {
                if (e) return ;
                while (flag[i]) i++;
                e=1;
            }
        }
        if (cnt<ret)
        {
            ret=cnt;
        }
        return ;
    }
    if (cnt>ret)
    {
        return ;
    }
    for (int i=1;i<=n;i++)
    {
        if (!flag[i])
        {
            flag[i]=1;
            dfs(step+1,cnt+dp[i][now[step]]);
            flag[i]=0;
        }
    }
}
int main() {
    freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
    scanf("%d%s",&n,s);
    for (int i=0;i<n;i++)
    {
        if (s[i]=='1')
        {
            now[++f]=i+1;
        }
    }
    for (int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a][b]=g[b][a]=1;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            dp[i][j]=dijstra(i,j);
        }
    }
    dfs(1,0);
    printf("%d",ret);
}