题面

问题描述

有 $n$ 个人，编号 $1$ 到 $n$ ，他们当中一些人认识另一些人。

现在要把这些人划分成两个非空队伍，使得每个人恰好属于其中的一个队伍，为了利于团队合作，要求每个队伍中任意两个人都互相认识。

你的任务就是:

1. 判断是否存在合法的分配方案，若不存在则输出字符串 No solution。
2. 若方案存在，则找到一种方案，使得两个队伍的人数之差最小，为了方便出题人准备数据以及降低本题的代码难度，你只需要输出这个差值。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来一共 $T$ 组数据，每组数据第一行一个正整数 $n$ 表示人数，接下来 $n$ 行 每行 $n$ 个用空格隔开的整数，第 $i$ 行第 $j$ 个数表示编号 $i$ 的人是否认识编号 $j$ 的 人，为 $1$ 表示认识，$0$ 表示不认识，保证 $a_{i,i}=1$。

$1 \leq T \leq 30, 1 \leq n \leq 100, a_{i,j} \in { 0,1 }, a_{i,i}=1$

输出格式

对每组数据输出一行表示答案。

样例数据

Input

2
5
1 1 1 0 1
1 1 1 1 1
1 1 1 0 1
1 1 1 1 0
1 1 1 1 1
3
1 0 0 
0 1 0
0 0 1

Output

1
No solution

题解

看到题目中认识的关系，我们就可以直接往图上抽象出这样的关系。

观察到样例数据中，$a_{i,j}$ 并不一定等于 $a_{j,i}$，而如果这两个不同为 $1$，那和两个 $0$ 的效果是等价的，因此我们可以先进行一个预处理，这样能建成一个无向图。（样例数据如图）：

似乎非常不直观，因为边太多了。。。

那怎么办呢，反向思考大法好。我们将不认识的连边再试试呢？

现在似乎好起来了，题目要求我们不能将不认识的两个人连起来，所以我们可以通过交替染色的方式来获取一种方案，下面的图中用紫、绿表示分组。

不难发现，正常情况下只有当遇到奇环时（如样例2，下图）才会无法将两个不认识的人分到两组。

此时我们无法对 $3$ 号点进行染色。

所以这种情况直接输出 No solution。

反之则能够直接找到一种方案，并且对于这个联通块来讲是唯一方案。

然后题目要求我们输出最小差值，对于单个联通块我们可以直接得到，最小差值即为当前两组的差值。

而对于所有联通块，我们则需要利用到多米诺骨牌这道题的背包转移方法来解决。其实当做完了这道题的以上步骤，本质上就和多米诺骨牌那道题一样了，都是将数据翻转后加到一起使得差值最小。

转移部分代码如下：($can_{i,j}$ 表示考虑前 $i$ 个联通块，能否使差值为 $j$; $cnt_{i,0/1}$ 表示第 $i$ 个联通块两种颜色的数量)

int can[110][110];
memset(can,0,sizeof can);
can[0][0]=1;
for(int i=1;i<=tot;++i){
    int delta=abs(cnt[i][0]-cnt[i][1]);
    for(int j=0;j<n;++j){
        can[i][j+delta]|=can[i-1][j];
        can[i][abs(j-delta)]|=can[i-1][j];
    }
}