@[Tarjan90°](/space/show?uid=80025)
by Brandon鹏 @ 2018-09-27 18:52:00
@[追风の裙子桑](/space/show?uid=89177)
by Brandon鹏 @ 2018-09-27 18:52:46
求救
by Brandon鹏 @ 2018-09-27 18:52:53
不在本学校就读的人要宿舍，本来就在学校就读并且要呆在学校的人也要宿舍。只要是不是本学校的人就是要拜访的人。@[Brandon鹏](/space/show?uid=86154)
by Kalista @ 2018-09-27 18:57:15
拜访别人的人
by Kalista @ 2018-09-27 18:58:43
@[Kalista](/space/show?uid=47350) 谢谢大佬帮助
by Brandon鹏 @ 2018-09-27 18:58:54
啊不用@[Brandon鹏](/space/show?uid=86154)
by Kalista @ 2018-09-27 18:59:14
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
queue<int >q;
const int INF=999999999;
int n;
int a[50][50];
int T;
int head[1001];
int standard;
struct node
{
int s;
int e;
int w;
int f;
int fan;
int next;
}edge[1000001];
int school[100001];
int home[100001];
int cnt;
int dis[1001];
int book[1001];
int sum;
int f[1001];
void add(int s,int e,int w,int f)
{
cnt++;
edge[cnt].s=s;
edge[cnt].e=e;
edge[cnt].w=w;
edge[cnt].f=f;
edge[cnt].fan=cnt+1;
edge[cnt].next=head[s];
head[s]=cnt;
cnt++;
edge[cnt].e=s;
edge[cnt].s=e;
edge[cnt].w=0;
edge[cnt].f=-f;
edge[cnt].fan=cnt-1;
edge[cnt].next=head[e];
head[e]=cnt;
}
void spfa(int s)
{
for(int i=0;i<=n*2+1;i++)
{
dis[i]=INF;
book[i]=0;
}
dis[s]=0;
q.push(s);
book[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
book[u]=0;
if(dis[u]==INF)
{
continue;
}
for(int t=head[u];t;t=edge[t].next)
{
if(edge[t].w<=0)
{
continue;
}
int v=edge[t].e;
if(dis[v]>dis[u]+edge[t].f)
{
dis[v]=dis[u]+edge[t].f;
f[v]=t;
if(!book[v])
{
book[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(home,0,sizeof(home));
memset(school,0,sizeof(school));
memset(head,0,sizeof(head));
memset(edge,0,sizeof(edge));
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
memset(book,0,sizeof(book));
cnt=0;
sum=0;
standard=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&school[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&home[i]);
}
for(int i=1;i<=n;i++)
{
if(school[i]==1&&home[i]==0)
{
standard++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
add(i,i+n,1,1);
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i][j])
{
add(i,j+n,1,1);
}
}
}
for(int i=1;i<=n;i++)
{
if(school[i]==1)
{
add(i+n,n*2+1,1,1);
}
}
for(int i=1;i<=n;i++)
{
if((school[i]&&!home[i])||!school[i])
{
add(0,i,1,1);
}
}
while(1)
{
spfa(0);
if(dis[n*2+1]>=INF)
{
break;
}
int k=n*2+1;
int minn=INF;
int p=k;
k=f[k];
while(k)
{
minn=min(minn,edge[k].w);
p=edge[k].s;
k=f[p];
}
p=n*2+1;
k=f[p];
while(k)
{
edge[k].w-=minn;
edge[edge[k].fan].w+=minn;
p=edge[k].s;
k=f[p];
}
sum+=minn;
}
if(sum>=standard)
{
printf("^_^\n");
}
else
{
printf("T_T\n");
}
}
return 0;
}
```
大佬能看一下我的初始化或者哪里写错了吗？全WA（我用的是费用流跑最大流）@[Kalista](/space/show?uid=47350)
by Brandon鹏 @ 2018-09-27 19:07:17
你得给我慢慢看。。我等下私信吧。。
by Kalista @ 2018-09-27 19:18:14
有必要费用流吗。。这不直接套网络流或者二分图板子就可以了吗。。
by Kalista @ 2018-09-27 19:21:06