【LSOIT3】天气之子 ---题解

题目传送门

【我叫阳菜。请多关照，帆高。】

【她一直不断的祈祷着，一边不断地穿过那个鸟居。】

【我做了个梦，初见你时，就像是迷途的小猫一样。】

【而你却帮我找到了存在的意义。】

【呐，马上要开始放晴了哦。】

这个题其他做法不知道怎么搞，暴力的话也不知道能过几个点，但是其实比较明显，仔细想可以想到是网络流，因为阳菜只会每次在一个区域，并且在那个区域不一定会使用超能力，用的话也只会用一次。所以我们得到了建图的方法。

• 超级源点向每个区域连边，因为只会去一次，所以容量为1。
• 每个区域向其所在的人连一条容量为1的边，因为只会帮一个人。
• 每个人向每个区域使用的超能力连一条边，容量为1，理由同上。

然后跑最大流？？

一开始我也是这样想的，可惜怎样都只有70分，但是，这是为什么。

如果建图没有问题的话，难道是我最大流跑错了？？

等等！“建图没问题”

建图真的没问题吗？

每个区域向其所在的人连一条容量为1的边，因为只会帮一个人。
每个人向每个区域使用的超能力连一条边，容量为1，理由同上。

但是，这样就无法保证每个人只有1次！所以要保证每个人至多帮了一次，我们需要，拆点---

将点拆成入点和出点！

入点再向出点连一条容量为1的边，这样就能保证每个人最多帮一次了。

割掉这条边也相当于不帮这个人。

最后就是代码了，注意每个区域和人和超能力的编号不要写错。

#include<bits/stdc++.h>
#define int long long 

using namespace std;

const int N=20010;
const int INF=1e15;

int n,p,q,S,T;
bool pd1[110][110],pd2[N][N];
int d[N<<2],now[N<<2];

struct liststar
{
    int u,v,w,nxt;
}e[N<<2];
int cnt=1,head[N<<2];
void add(int u,int v,int w){e[++cnt].nxt=head[u];head[u]=cnt;e[cnt].v=v;e[cnt].w=w;}
void addd(int u,int v,int w){add(u,v,w);add(v,u,0);}

int read()
{
    int x=0,s=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')s=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-48;
    return x*s;
}

void init()
{
    n=read();p=read();q=read();S=0;T=80001;//T设大一点以防中间有点过来
    for(int i=1;i<=p;i++)addd(S,i,1);
    for(int i=1;i<=n;i++)addd(p+q+i,p+q+i+n,1);//拆点
    for(int i=1;i<=n;i++)
        for(int l=1;l<=p;l++)
        {
            bool pd=read();
            if(pd)addd(l,p+q+i,1);
        }
    for(int i=1;i<=n;i++)
        for(int l=1;l<=q;l++)
        {
            bool pd=read();
            if(pd)addd(p+q+i+n,p+l,1);
        }
    for(int i=1;i<=q;i++)addd(p+i,T,1);
}

bool bfs()
{
    queue<int>q;
    memset(d,0,sizeof(d));
    d[S]=1;now[S]=head[S];
    q.emplace(S);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u],y;i;i=e[i].nxt)
            if(e[i].w && !d[y=e[i].v])
            {
                now[y]=i;
                d[y]=d[u]+1;
                q.emplace(y);
                if(y==T)return true;
            }
    }
    return false;
}

int dinic(int x,int flow)
{
    if(x==T)return flow;
    int res=flow;
    for(int i=head[x],y;i;i=e[i].nxt)
    {
        now[x]=i;
        if(e[i].w && d[y=e[i].v]==d[x]+1)
        {
            int t=dinic(y,min(e[i].w,res));
            if(!t)d[y]=0;
            res-=t;e[i].w-=t;e[i^1].w+=t;
        }
    }
    return flow-res;
}

signed main()
{
    init();
    int res=0,maxn=0;
    while(bfs())while(res=dinic(S,INF))maxn+=res;//dinic板子
    cout<<maxn;
    return 0;
}