洛谷4843 BZOJ2502 清理雪道

男娘i 2022-10-02 14:49 23阅读 0赞

有源汇有上下界的最小可行流。

YY一下建图应该很好搞吧（？

就是对于每个雪道都是\[1,inf\]然后源点到所有点都是\[0,inf\]所有点到汇点都是\[0,inf\]

这样的话跑一个有源汇上下界最小可行流就可以了

有关于这个可以看liu\_runda神犇的介绍 非常直观易懂

最开始先建超级源汇 跑可行流得到一个基础流量 然后反向在残余网络上跑最大流减去即可

注意最后的时候是需要**反向**在残余网络上跑的 不要忘记交换源汇

代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//Love and Freedom.
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #define inf 20021225
    #define ll long long
    #define N 200
    #define M 40000
    using namespace std;
    
    struct edge{
         int lt,to,f;}e[M<<1];
    int cnt=1,in[N],dep[N],s,t,ss,tt;
    queue<int> q;
    void add(int x,int y,int f)
    {
        e[++cnt].to = y; e[cnt].lt = in[x]; in[x] = cnt; e[cnt].f = f;
        e[++cnt].to = x; e[cnt].lt = in[y]; in[y] = cnt; e[cnt].f = 0;
    }
    bool bfs()
    {
        while(!q.empty())    q.pop();
        q.push(s); memset(dep,0,sizeof(dep)); dep[s] = 1;
        while(!q.empty())
        {
            int x = q.front(); q.pop();
            for(int i=in[x];i;i=e[i].lt)
            {
                int y = e[i].to; if(dep[y] || !e[i].f)    continue;
                dep[y] = dep[x]+1; q.push(y);
                if(y==t)    return 1;
            }
        }
        return 0;
    }
    int dfs(int x,int f)
    {
        if(!f || x==t)    return f;
        int flow = f;
        for(int i=in[x];i;i=e[i].lt)
        {
            int y = e[i].to;
            if(dep[y] == dep[x]+1 && e[i].f && flow)
            {
                int cur = dfs(y,min(flow,e[i].f));
                e[i^1].f += cur; e[i].f -= cur;
                flow -= cur; if(!flow)    return f;
            }
        }
        dep[x] = -1; return f-flow;
    }
    int dinic()
    {
        int ans = 0;
        while(bfs())    ans+=dfs(s,inf);
        return ans;    
    }
    int most[M],f[N],n;
    void del(int x)
    {
        for(int i=in[x];i;i=e[i].lt)
            e[i].f = e[i^1].f = 0;
    }
    int main()
    {
        s = N-6; t = s+1; ss = t+1; tt = ss+1;
        scanf("%d",&n);
        for(int x=1;x<=n;x++)
        {
            int i,y;    scanf("%d",&i);
            while(i--)
            {
                scanf("%d",&y); f[y]++; f[x]--;
                add(x,y,inf);
            }
        }
        for(int x=1;x<=n;x++){add(s,x,inf); add(x,t,inf);}
        for(int i=1;i<=n;i++)
        {
            if(f[i]<0)    add(i,tt,-f[i]);
            else    add(ss,i,f[i]);
        }
        add(t,s,inf); int tmps = s,tmpt = t;
        s = ss; t = tt; int flow = dinic();
        flow = e[cnt].f; e[cnt].f = e[cnt-1].f = 0;
        del(ss); del(tt); s = tmpt,t = tmps;
        printf("%d\n",flow-dinic());
        return 0;
    }

转载于:https://www.cnblogs.com/hanyuweining/p/10371831.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/3f38536577dd4d35a6aa29ec445908d4.png