显然可以看作竞赛图上的最大流，考虑转化为最小割。
令 \(S\) 为包含 \(s_1,s_2,\dots,s_k\) 但不包含 \(t_i\) 的点集，\(T=\{1,2,\dots,n\}\backslash S\)，则代价为 \(\sum_{x\in S}\sum_{y\in T}v_{x,y}\)，记为 \(f(S,T)\)。
放在竞赛图上可以找到一些性质：\(f(S,T)+f(T,S)=|S|\times |T|,f(S,T)-f(T,S)=\sum_{x\in S}\text{out}_x-\text{in}_x\)，由这两个值可以得到 \(f(S,T)\)。于是将所有点按 \(\text{out}_x-\text{in}_x\) 从小到大排序，然后贪心取就做完了，时间复杂度 \(\mathcal O(n(n+m))\)。
参考代码：
#include<bits/stdc++.h>
#define mxn 3003
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n,m,st,sm,ct,ans,c[mxn],p[mxn];
char s[mxn][mxn];
bool v[mxn];
signed main(){scanf("%d%d",&n,&m);rep(i,1,n){scanf("%s",s[i]+1);rep(j,1,n)if(i!=j){if(s[i][j]=='1')c[i]++;else c[i]--;}p[i]=i;}sort(p+1,p+n+1,[](int x,int y){return c[x]<c[y];});int t,x;while(m--){rep(i,1,n)v[i]=0;scanf("%d%d",&st,&t);sm=0,ct=t;while(t--)scanf("%d",&x),v[x]=1,sm+=c[x];ans=sm+ct*(n-ct);rep(i,1,n){x=p[i];if(x==st||v[x])continue;sm+=c[x],ct++;ans=min(ans,sm+ct*(n-ct));}cout<<(ans>>1)<<'\n';}return 0;
}