en，被JD大佬强行思考了一下建图，趁着记得，写一篇题解
注：前面二分图解法，后面网络流解法
题目
二分图解法
提前处理好位置与人的关系，跑匈牙利算法，注释在代码上
题解
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;
int n,k,m,vis[maxn],match[maxn],ans,g[maxn][maxn],a[maxn],b[maxn];
int find(int u){
for(int i=1;i<=n;i++){
if(g[u][i]&&!vis[i]){//u这个位置能坐i这个人且i这个人没坐其他位置
vis[i]=1;
if(!match[i] || find(match[i])){//如果这没人，或这个位置有其他人可以
match[i] = u;//i可以坐这个位置
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d",&m);
while(m--){
memset(g,0,sizeof(g));
memset(match,0,sizeof(match));//初始化
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
if(a[i]==1&&b[i]==0) g[i][i]=1;//本班人能坐自己位置
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int x;scanf("%d",&x);
if(x==1&&a[j]==1) g[i][j]=1;//j可以坐在i这个位置
}
}
bool flag=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if((!a[i]) || (a[i]&&!b[i])){//i这个人是外班的或分班前后依旧是本班的人都需要找个位置
if(!find(i)){
flag=1;//有人没座,break
break;
}
}
}
printf("%s\n",flag?"T_T":"^_^");
}
return 0;
}
网络流解法
\(S\) 向每个座位连边，座位向能坐座位的人连边，人像 \(T\) 连边，边权均为一，最大流即为能找到座位的人数，与总座位数比较
即可，注意细节和上面二分图解法细节一致
题解——代码来自JD大佬
#include <bits/stdc++.h>
#define N 100005
#define inf 1e5
using namespace std;
int n,m,S,T,dis[N],sum,a[N],b[N],c[55][55],Q;
queue < int > q;
struct Edge{int next,to,dis,flow;}edge[N];
int head[N],now[N],cnt = 1;
void add(int from,int to,int dis){
edge[++cnt] = (Edge){head[from],to,dis,0};
head[from] = cnt;
}
void Input(){
memset(head,0,sizeof(head));cnt = 1;
scanf("%d",&n);S = 0,T = 2 * n + 1,sum = n;
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i ++) {scanf("%d",&b[i]);if(a[i] == 1 and b[i] == 1) sum --;}
for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) scanf("%d",&c[i][j]);
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
if((c[i][j] == 1 or i == j) and a[i] == 1) add(i,j + n,1),add(j + n,i,0);
}
}
for(int i = 1;i <= n;i ++) if(a[i] == 1) add(S,i,1),add(i,S,0);
for(int i = 1;i <= n;i ++) if(a[i] == 0 or b[i] == 0) add(i + n,T,1),add(T,i + n,0);
}
bool bfs(){
for(int i = S;i <= T;i ++) dis[i] = 0;
dis[S] = 1,q.push(S);
while(!q.empty()){
int x = q.front();q.pop();
now[x] = head[x];
for(int i = head[x];i;i = edge[i].next){
int y = edge[i].to;
if(!dis[y] and edge[i].dis > edge[i].flow){
dis[y] = dis[x] + 1;
q.push(y);
}
}
}
return dis[T];
}
int dfs(int x,int flow){
if(x == T or !flow) return flow;
int res = 0;
for(int i = now[x];i;i = edge[i].next){
now[x] = i;
int y = edge[i].to,d;
if(dis[y] == dis[x] + 1 and (d = dfs(y,min(edge[i].dis - edge[i].flow,flow - res)))){
edge[i].flow += d,edge[i ^ 1].flow -= d;
res += d;if(res == flow) break;
}
}
return res;
}
void work(){
int ans = 0;
while(bfs()) ans += dfs(S,inf);
if(ans == sum) puts("^_^");
else puts("T_T");
}
signed main(){scanf("%d",&Q);while(Q --){Input();work();}return 0;}