#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
//多组数据 的一定要注意清零
int n,d[
1005],line[
1005][
1005],b[
1005],no[
1005],vis[
1005];
int s,t,kk,tot;
queue<
int>
q;
int bfs()
{
memset(vis,0,
sizeof vis);
memset(d,0,
sizeof d);
while(!q.empty()) q.pop();
/
d[s]=
1;
vis[s]=
1;
q.push(s);
while(!
q.empty())
{
int u=
q.front();
// cout<<"u:"<<u<<endl;
q.pop();
for(
int v=
1;v<=t;v++)
//这个地方写成v<=n了
{
if(line[u][v]>
0 && !
vis[v]){
d[v]=d[u]+
1;
vis[v]=
1;
q.push(v);
if(v==t)
return 1;
}
}
}
return 0;
}
int dinic(
int u,
int res)
//没有优化的
{
if(u==t)
return res;
int sum=
0;
for(
int v=
1;v<=t;v++
)
{
// cur[u]=v;
if(d[u]+
1==d[v] && line[u][v]>
0 && res>
0)
{
int k=
dinic(v,min(res,line[u][v]));
line[u][v]-=
k;
line[v][u]+=
k;
sum+=
k;
res-=
k;
if(res==
0)
break;
}
}
return sum;
}
int main()
{
scanf("%d",&
kk);
while(kk--
)
{
memset(line,0,
sizeof line);
tot=
0;
scanf("%d",&n);s=
0;t=
2*n+
1;
for(
int i=
1;i<=n;i++
)
scanf("%d",&b[i]);
//1为在校学生
for(
int i=
1;i<=n;i++
)
scanf("%d",&
no[i]);
//前面这两个是决定超级源点到其他点的
int p;
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=n;j++
)
{
scanf("%d",&
p);
if(p==
1 &&
b[j])
{
line[i][j+n]=
1;
line[j+n][t]=
1;
}
if(b[i])
{
line[i][i+n]=
1;
line[i+n][t]=
1;
}
}
for(
int i=
1;i<=n;i++
)
{
if((b[i]==
1 && !no[i]) || !b[i])
//在校学生且不回家的+外校学生 才和源点连接
{
line[0][i]=
1;
tot++
;
}
}
//检查连线情况
// for(int i=0;i<=t;i++)
// for(int j=0;j<=t;j++)
// if(line[i][j]==1)
// cout<<i<<","<<j<<endl;
//检查bfs分层情况
// bfs();
// for(int i=0;i<=t;i++)
// cout<<i<<","<<d[i]<<endl;
// bfs();
// cout<<dinic(s,inf)<<endl;
// for(int i=0;i<=t;i++)
// for(int j=0;j<=t;j++)
// cout<<i<<","<<j<<","<<line[i][j]<<endl;
// bfs();
// cout<<dinic(s,inf)<<endl;
int flow=
0,mxflow=
0;
// for(int i=1;i<=t;i++)cur[i]=1;
while(bfs())
{
mxflow+=
dinic(s,inf);;
}
if(tot==
mxflow)
cout<<
"^_^"<<
endl;
else
cout<<
"T_T"<<
endl;
}
}
邻接表：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define inf 1e9
const int MAXN=
1005;
using namespace std;
int n,s,kk,tot,hd[MAXN],t;
int b[MAXN],no[MAXN],vis[MAXN],d[MAXN];
int cnt;
struct Edge{
int nxt,to,vl;
}edge[MAXN<<
1];
void add(
int u,
int v,
int w)
{
cnt++
;
edge[cnt].to=
v;
edge[cnt].nxt =
hd[u];
edge[cnt].vl=
w;
hd[u]=
cnt;
}
queue<
int>
q;
int bfs()
{
memset(vis,0,
sizeof vis);
memset(d,0,
sizeof d);
while(!
q.empty()) q.pop();
d[s]=
1;
vis[s]=
1;
q.push(s);
while(!
q.empty())
{
int u=
q.front();
q.pop();
for(
int i=hd[u];i;i=
edge[i].nxt)
{
int v=
edge[i].to;
if(!vis[v] && edge[i].vl>
0)
{
d[v]=d[u]+
1;
vis[v]=
1;
q.push(v);
if(v==t)
return 1;
}
}
}
return 0;
}
int dinic(
int u,
int res)
{
if(u==t)
return res;
int sum=
0;
for(
int i=hd[u];i;i=
edge[i].nxt)
{
int v=
edge[i].to;
if(d[u]+
1==d[v] && edge[i].vl>
0 && res>
0)
{
int k=
dinic(v,min(res,edge[i].vl));
edge[i].vl-=
k;
edge[i^
1].vl+=
k;
sum+=
k;
res-=
k;
if(res==
0)
break;
}
}
return sum;
}
int main()
{
scanf("%d",&
kk);
while(kk--
)
{
tot=
0;s=
0,t=
2*n+
1;
cnt=
1;memset(hd,
0,
sizeof hd);
scanf("%d",&
n);
for(
int i=
1;i<=n;i++
)
{
scanf("%d",&
b[i]);
if(b[i]) add(i+n,t,
1),add(t,i+n,
0);
}
for(
int i=
1;i<=n;i++
)
{
scanf("%d",&
no[i]);
if(!b[i] || (b[i] && !
no[i]))
{
add(s,i,1);
add(i,s,0);
tot++
;
}
}
int p;
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=n;j++
)
{
scanf("%d",&
p);
if(p || i==
j)
{
add(i,j+n,
1);
add(j+n,i,
0);
}
}
int mxflow=
0;
while(bfs())
{
mxflow+=
dinic(s,inf);
}
if(tot==
mxflow)
cout<<
"^_^"<<
endl;
else
cout<<
"T_T"<<
endl;
}
}
转载于:https://www.cnblogs.com/caterpillor/p/9250523.html
相关资源：各显卡算力对照表！
