2021百度之星初赛第二场 魔怔

思路：

图论。

实现：

 1 #include
 2 using namespace std;
 3 int p[1005];
 4 void init(int n){
 5     for(int i=1;i<=n;i++){
 6         p[i]=i;
 7     }
 8 }
 9 int find(int x){
10     if(p[x]==x){
11         return x;
12     }
13     return p[x]=find(p[x]);
14 }
15 void uni(int x,int y){
16     x=find(x),y=find(y);
17     p[x]=y;
18 }
19 int main(){
20     //freopen("in.txt","r",stdin);
21     int t;cin>>t;
22     while(t--){
23         int n,s;cin>>n>>s;
24         vector<int>d(n+1,0);
25         init(n);
26         set<int>st;
27         int w=0;
28         for(int i=1;i<=n-1;i++){
29             string t;cin>>t;
30             for(int j=0;j){
31                 int to=j+1;
32                 if(t[j]=='0'){
33                     d[i+1]++;
34                     d[to]++;
35                     uni(i+1,to);
36                     st.insert(i+1);
37                     st.insert(to);
38                     w++;
39                 }
40             }
41         }
42         int c=0;
43         for(int i=1;i<=n;i++){
44             if(d[i]&1){
45                 c++;
46             }
47         }
48         if(c>2 or c==1){
49             cout<<-1<<endl;
50         }
51         else if(c==2 and d[s]%2==0){
52             cout<<-1<<endl;
53         }
54         else{
55             set<int>tmp;
56             for(auto it:st){
57                 tmp.insert(p[it]);
58             }
59             int res=(tmp.size()-1)*2+w;
60             if(!st.count(s)){
61                 res+=2;
62             }
63             cout<endl;
64         }
65     }
66     return 0;
67 }