比赛 |
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;
}