在dalao帮助下终于懂了建图操作~~

不懂网络流先去板子

很容易想到网络流跑一遍最大流

所以这题难点大概就是建图

所以我卡了很久

大家都能想到这个建图

其中1.2为房，5 6为人，3.4为菜，500为终点

然后高兴去交 60分emmmmmm

百思不得其解

参考daolao后知道了一些神奇的情况

感谢这位dalao

像这种情况

答案应该是1
但这个图跑下来是3

于是就不对了

仔细思考就有了建两个人的点的方法

一个连房子
一个连菜

再加一个点来限流的操作可以保证每个人只选一房一菜

图如下

于是就成了！！！！！！
然后就AC了
就是这样

虽然我不懂为啥有时建图一样却是错的，大概要注意一下建图顺序大家摸索摸索
总之很神奇

样例最终图如下

看起来和第一个图没啥差别所以我卡了很久

然后代码就很简单了
这里dinic

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#define N 10003
#define INF (1<<30)
using namespace std;
int head[N],deep[N],ans;
int n,m,n1,m1,m0,ed,st;
int cnt=1;//注意从2开始存，保证异或

struct node
{
    int to,w,fr;
    int _nt;
}edge[N];
void add(int x,int y,int z)//这里前向星
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt]._nt=head[x];
    edge[cnt].w=z;
    head[x]=cnt;
}

int bfs(int s,int t)//传统dinic不解释
{
    memset(deep,0,sizeof(deep));
    queue<int> q;
    q.push(s);
    deep[s]=1;
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i!=-1;i=edge[i]._nt)
        {
            int v=edge[i].to;
           if(deep[v]||edge[i].w<=0)continue;
            deep[v]=deep[tmp]+1;
            q.push(v);
            if(v==t)return 1;
        }

    }
    if(deep[t])return 1;
    else return 0;
}
int dfs(int u,int ed,int flow)
{
    if(u==ed)return flow;
    int ans=0;
    for(int i=head[u];i!=-1&&ans<flow;i=edge[i]._nt)
    {
        int v=edge[i].to;
        if(deep[v]!=deep[u]+1)continue;
        if(!edge[i].w)continue;
        int x=dfs(v,ed,min(edge[i].w,flow-ans));
        edge[i].w-=x;
        edge[i^1].w+=x;
        ans+=x;

    }
    return ans;
}

int dinic(int s,int t)//dinic操作
{
    int sum=0;
    while(bfs(s,t))
        sum+=dfs(s,t,INF);
    return sum;

}
int main()
{

    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m1,&m0);
    st=0;ed=500;//建源点和汇点
    for(int i=1;i<=m1;i++)//首先建房
    {
        add(0,i,1);
        add(i,0,0);
    }
    for(int i=1;i<=m0;i++)//再建菜
    {
        add(i+m1,ed,1);
        add(ed,i+m1,0);

    }
    for(int i=1;i<=n;i++)//再建两个人
    {
        add(i+m1+m0,i+m1+m0+n,1);
        add(i+m1+m0+n,i+m1+m0,0);
    }
    for(int i=1;i<=n;i++)//再连边，房子的边
    {
        for(int j=1;j<=m1;j++)
        {
            int x;
            scanf("%d",&x);
            if(x==1)
                add(j,i+m1+m0,1),add(i+m1+m0,j,0);
        }
    }
    for(int i=1;i<=n;i++)//再连菜
    {
        for(int j=1;j<=m0;j++)
        {
            int x;
            scanf("%d",&x);
            if(x==1)
             add(i+n+m1+m0,m1+j,1),add(m1+j,i+n+m1+m0,0);


        }
    }

    printf("%d",dinic(st,ed));//直接输出

    return 0;
}

这题可能有玄学建图顺序，大概这样比较保险

然后就讲完了

emmmmmmmmmmm真长（苦笑）

顺便双倍经验

估计都能懂吧~