比赛 2024暑假C班集训C 评测结果 WWWWTTTTTT
题目名称 喵星人集会 最终得分 0
用户昵称 彭欣越 运行时间 12.718 s
代码语言 C++ 内存使用 3.25 MiB
提交时间 2024-07-12 11:59:22
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,head[1010],tot,cnt,b[1010],res=1e9+10,mk[1010];
char a[1010];
struct node {
    int idx,nxt;
}e[1010];
void add (int a,int b) {
    e[++tot].idx=b;
    e[tot].nxt=head[a];
    head[a]=tot;
}
bool check () {
    int maxx=0,minn=1e9+10;
    for (int i=1;i<=cnt;i++) {
        maxx=max(maxx,b[i]);
        minn=min(minn,b[i]);
    }
    cout << maxx <<' '<< minn <<endl;
    if (maxx-minn+1==cnt) return 1;
    return 0;
}
void dfs (int idx) {
    if (idx>=res) return;
    if (check()) {
        res=min(res,idx);
        return;
    }
    for (int i=1;i<=cnt;i++) {
        for (int j=head[i];j;j=e[j].nxt) {
            if (mk[e[j].idx]==1) continue;
            int t=b[i];
            b[i]=e[j].idx;
            mk[b[i]]=1;
            dfs(idx+1);
            mk[b[i]]=0;
            b[i]=t;
        }
    }
}
int main () {
    freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        if (a[i]=='1') b[++cnt]=i;
    }
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    dfs(0);
    cout << res <<endl;
    return 0;
}