先直接给出思路，把这个矩阵建成一个完全二分图，如果\(a_{i,j}=1\)的话从左边的i连向右边的j，否则从右边的j连向左边的i，此时左边\(i\)的出度表示第\(i\)行的\(1\)的个数，右边\(j\)的出度表示第\(j\)列1的个数。我们发现，如果图中存在一个环，那么将环上的边全部翻转所有点的度数依然不变，但那些翻转的边就不固定了，所以对于一张图，他的答案就是非环上边的个数。我们考虑dp，\(dp_{i,j,k}\)表示考虑了左边\(i\)个点，右边\(j\)个点，有\(k\)个边是确定的是否可行。转移的时候枚举新加的联通分量左边占了\(x\)个，右边占了\(y\)个，那么多出来的固定边就是\(i*y+j*x\)。
不容易想到二分图定向。只能说二分图完全图这一模型恰好完美的用在此题中了。