网络流24题

网络流24题 1/24 洛谷P2756 飞行员配对方案问题(二分图匹配)

题目思路

二分图匹配的板子题,用dinic求解时,先将源点连所有左部点,汇点连所有右部点,容量全设为1,然后连上所有题目给出的边,这样就建好图了。
跑dinic后最大流就是二分图最大匹配值。
题目还要求输出左部和右部点相连情况,开始在想用一个fa数组记录连接情况,每次dfs更新,但是wa了3、4个点,估计是撤销操作的影响。其实只要判断左部点连向右部的正向边是否为0就好,为零输出两个端点。

网络流24题 2/24 洛谷P3254 圆桌问题(二分图多重匹配)

题目思路

建图基本跟上题一样,只是源点到左部点,右部点到汇点的容量变一下就行了。
题目要求判断是否成立,成立就输出所有*的就餐位置
我们让餐桌作为左部点,单位表示右部点,我们最后只需要判断右部点到汇点边的容量是否都为0,都为0说明说明成立。
然后我们判断就餐位置就跟上题类似,判断右部点连向左部点的边是否为1,为1说明正边被走过,输出左部点。
很坑的是这题是先输入m再输入n,要注意这里。

ac代码

int cnt=1;
struct node
{
    int to,next;
    int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int fa[maxn];
int vis[maxn];

void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=first[u];
    first[u]=cnt;
}

inline bool bfs()
{
    ms(dep,-1);
    dep[s]=0;
    memcpy(cur,first,sizeof(first));
    queue<int>q;
    q.push(s);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=first[u];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            int vol=e[i].w;
            if(vol>0&&dep[to]==-1)
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t]!=-1;
}

inline int dfs(int u=s,int flow=inf)
{

    if(u==t)
        return flow;
    int last=flow;
    for(int i=cur[u];i!=-1&&last;i=e[i].next)
    {
        cur[u]=i;
        int to=e[i].to;
        int vol=e[i].w;

        if(vol>0&&dep[to]==dep[u]+1)
        {
            int c=dfs(to,min(vol,last));
            fa[u]=to;
            last-=c;
            e[i].w-=c;
            e[i^1].w+=c;

        }else
        {
            fa[u]=-1;
        }
    }
    return flow-last;
}
inline void dinic()
{

    while(bfs())
    {
        dfs();
    }
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=first[i];j!=-1;j=e[j].next)
        {
            if(e[j].to!=t)continue;
            if(e[j].w!=0)
            {
                flag=1;
            }
        }
    }
    if(flag==1)printf("0\n");
    else
    {
        printf("1\n");
        for(int i=1;i<=n;i++)
        {

            for(int j=first[i];j!=-1;j=e[j].next)
            {
                if(e[j].to==t)continue;
                if(e[j].w==1)
                {
                    printf("%d ",e[j].to-n);
                }
            }
            printf("\n");
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    s=0,t=m+n+1;
    ms(first,-1);
    ms(fa,-1);
    for(int i=1;i<=n;i++)
    {
        int w;
        scanf("%d",&w);
        add(i,t,w);
        add(t,i,0);
    }

    for(int i=1;i<=m;i++)
    {
        int w;
        scanf("%d",&w);
        add(i+n,s,0);
        add(s,i+n,w);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            add(i,j+n,0);
            add(j+n,i,1);
        }
    }
    dinic();

}

网络流24题 3/24 洛谷P2763 试题库问题(二分图多重匹配)

题目思路

基本思路跟上题一样,但是建图的时候源点连向题目的边容量应该为1
这里没考虑清楚,wa了一发

网络流24题 4/24 洛谷P2764 最小路径覆盖问题(最小路径不相交覆盖)

题目思路

将每个点拆成两份x1,x2,源点连向x1,x2连向汇点,容量均为1。
在根据题目给的边,将端点连起来,容量也为1。
我们对这个图跑最短路,跑出来的最大流就是原图中点的最大匹配值
又因为最小路径覆盖=原图节点数-新图最大匹配数
所以我们就能够的到答案了。
输出路径见代码

ac代码


int cnt=1;
struct node
{
    int to,next;
    int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];

int vis[maxn];

void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=first[u];
    first[u]=cnt;
}

inline bool bfs()
{
    ms(dep,-1);
    dep[s]=0;
    memcpy(cur,first,sizeof(first));
    queue<int>q;
    q.push(s);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=first[u];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            int vol=e[i].w;
            if(vol>0&&dep[to]==-1)
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t]!=-1;
}

inline int dfs(int u=s,int flow=inf)
{

    if(u==t)
        return flow;
    int last=flow;
    for(int i=cur[u];i!=-1&&last;i=e[i].next)
    {
        cur[u]=i;
        int to=e[i].to;
        int vol=e[i].w;

        if(vol>0&&dep[to]==dep[u]+1)
        {
            int c=dfs(to,min(vol,last));

            last-=c;
            e[i].w-=c;
            e[i^1].w+=c;

        }
    }
    return flow-last;
}
inline void dinic()
{
    int ans=0;

    while(bfs())
    {
        ans+=dfs();
    }


    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==1)continue;
        int x=i;
        int flag=1;
        while(1)
        {
            if(flag==0)break;
            flag=0;
            printf("%d ",x);
            vis[x]=1;
            for(int j=first[x];j!=-1;j=e[j].next)
            {
                int to=e[j].to;
                if(e[j].w==0&&vis[to]==0&&to!=s)
                {
                    x=to-n;
                    flag=1;
                    break;
                }
            }
        }
        printf("\n");
    }
    printf("%d\n",n-ans);


}

int main()
{
    scanf("%d%d",&n,&m);
    s=0,t=2*n+1;
    ms(first,-1);
    for(int i=1;i<=n;i++)
    {
        add(s,i,1);
        add(i,s,0);
        add(i+n,t,1);
        add(t,i+n,0);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v+n,1);
        add(v+n,u,0);
    }
    dinic();

}



网络流24题 5/24 洛谷P2765 魔术球问题

题目思路

题目乍一看会有贪心等想法,其实确实也有这种解法,但作为网络流24题中的一个,还是用网络流求解。
因为题目给出要求每个柱子上的点之间和为完全平方数,所以我们可以根据这个条件建边。
题目要求按编号从小到大将球放上柱子,那么我们就枚举球的编号。每次加入后,将球连向源点汇点,再将已经放入的能和它组成完全平方数的点连向它。然后我们每次枚举建完图后都跑一边dinic,当我们得不到值(即该点加入后没有新的匹配生成)时我们将这个点放到新的柱子的第一位。如果柱子数大于题目给的n,那么说明当前值无法放入了,直接退出枚举。我们就得到了需要的值。
这题建议不要用memset来初始化,不然会t。
还有不用当前弧优化能过,用memcpy来进行弧优化的初始化会t,就很神奇。

ac代码

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1h
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
#define pb(x) push_back(x)
using namespace std;
const int maxn = 2e6+10;
const int inf = 1e9;
const ll llinf =1e18+10;
const ll mod = 1e9+7;


int cnt=1;
struct node
{
    int to,next;
    int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int top[maxn];
int sp[maxn];
int now,tot;

void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=first[u];
    first[u]=cnt;
}

inline bool bfs()
{
    for(int i=1;i<=100010;i++)dep[i]=-1;
    dep[s]=0;
    queue<int>q;
    q.push(s);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=first[u];i;i=e[i].next)
        {
            int to=e[i].to;
            int vol=e[i].w;
            if(vol>0&&dep[to]==-1)
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t]!=-1;
}

inline int dfs(int u=s,int flow=inf)
{

    if(u==t)
        return flow;
    int last=flow;
    for(int i=first[u];i&&last;i=e[i].next)
    {
        //cur[u]=i;
        int to=e[i].to;
        int vol=e[i].w;

        if(vol>0&&dep[to]==dep[u]+1)
        {
            int c=dfs(to,min(vol,last));

            last-=c;
            e[i].w-=c;
            e[i^1].w+=c;

        }
    }
    return flow-last;
}
inline int dinic()
{
    int ans=0;

    while(bfs())
    {
        ans+=dfs();
    }


    return ans;


}

int main()
{
    int n;
    scanf("%d",&n);

    s=0;
    t=100*1000+1;

    tot=0,now=0;
    while(tot<=n)
    {
        ++now;

        add(s,now*2,1);
        add(now*2,s,0);
        add(now*2+1,t,1);
        add(t,now*2+1,0);

        for(int i=sqrt(now);i*i<2*now;i++)
        {
            if(i*i<=now)continue;
            int tem=i*i-now;
            add(tem*2,now*2+1,1);
            add(now*2+1,tem*2,0);
        }
        int tem=dinic();
        if(tem==0)
            top[++tot]=now;
    }
    printf("%d\n",now-1);
    for(int i=1;i<=n;i++)
    {
        int x=top[i];
        while(1)
        {
            printf("%d ",x);
            int flag=0;
            for(int j=first[2*x];j;j=e[j].next)
            {
                int to=e[j].to;
                if(to==s)continue;
                if(e[j].w==0)
                {
                    x=(to-1)/2;
                    flag=1;
                    break;
                }

            }
            if(flag==0)
                break;

        }
        printf("\n");
    }
}

总结

这题开始想的时候枚举建图的方式都搞错了,还是要记住二分图建图的模型和它代表的意义,不要跟别普通的图搞混。
尽量少用memset,几组数据都是删前tle,删完之后只有30ms

网络流24题 6/24 洛谷P2766 最长不下降子序列问题

题目思路

题目给出了三问。
因为数据较小,所有第一问可以用n方dp求出答案s。
对于第二问,第三问我们用网络流求解。
首先对于第二问,每个点都只出现在一个序列里面,所以考虑拆点。
我们将点i拆成i_a和i_b两个点,i_a连向i_b并且容量为1。
我们可以根据dp的结果来决定其他的连线
我们首先让dp[i]==1的点i跟s连一条边,容量为1,s流向i。
然后让dp[i]==s的点i跟t连一条边,容量为1,i流向t。
然后对满足i<j,a[i]<a[j],dp[j]=dp[i]+1的i、j两点连边。
这样我们就建好图了,跑完最短路就能得到第二问的答案。
第三问跟第二问类似,只需要把s连向1和n,1内部连线,n内部连线,1和n连向t的边容量全部变成inf就好了。但是这样会出现一个特殊情况,就是s = = 1时,图的结果会是inf,而不是答案1。所以我们需要特判这个情况。

ac代码

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1h
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
#define pb(x) push_back(x)
using namespace std;
const int maxn = 2e6+10;
const int inf = 0x7f7f7f7f;
const ll llinf =1e18+10;
const ll mod = 1e9+7;


int cnt=1;
struct node
{
    int to,next;
    int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int top[maxn];
int dp[maxn];
int a[maxn];
int now,tot;

void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=first[u];
    first[u]=cnt;
}

inline bool bfs()
{
    ms(dep,-1);
    dep[s]=0;
    queue<int>q;
    q.push(s);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=first[u];i;i=e[i].next)
        {
            int to=e[i].to;
            int vol=e[i].w;
            if(vol>0&&dep[to]==-1)
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t]!=-1;
}

inline int dfs(int u=s,int flow=inf)
{

    if(u==t)
        return flow;
    int last=flow;
    for(int i=first[u];i&&last;i=e[i].next)
    {
        //cur[u]=i;
        int to=e[i].to;
        int vol=e[i].w;

        if(vol>0&&dep[to]==dep[u]+1)
        {
            int c=dfs(to,min(vol,last));

            last-=c;
            e[i].w-=c;
            e[i^1].w+=c;

        }
    }
    return flow-last;
}

inline int dinic()
{
    int ans=0;

    while(bfs())
    {
        //print1;
        ans+=dfs();
    }


    return ans;


}

int main()
{
    scanf("%d",&n);
    s=0,t=n*2+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int ss=0;
    for(int i=1;i<=n;i++)dp[i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>=a[j])
                dp[i]=max(dp[i],dp[j]+1);

        }
        ss=max(ss,dp[i]);
    }
    printf("%d\n",ss);
    for(int i=1;i<=n;i++)
    {
        add(i,i+n,1);
        add(i+n,i,0);
        if(dp[i]==1)
        {
            add(s,i,1);
            add(i,s,0);
        }
        if(dp[i]==ss)
        {
            add(i+n,t,1);
            add(t,i+n,0);
        }
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]<=a[j]&&dp[j]==dp[i]+1)
            {
                add(i+n,j,1);
                add(j,i+n,0);
            }
        }
    }
    int ans=dinic();
    printf("%d\n",ans);
    cnt=1;
    if(ss==1)
    {
        set<int>st;
        for(int i=1;i<=n;i++)
            st.insert(a[i]);
        printf("%d\n",st.size());
    }else
    {
        ms(first,0);
        for(int i=1;i<=n;i++)
        {
            if(dp[i]==1)
            {
                if(i==1||i==n)
                {
                    add(s,i,inf);
                    add(i,s,0);
                }else
                {
                    add(s,i,1);
                    add(i,s,0);
                }
            }
            if(dp[i]==ss)
            {
                if(i==n||i==1)
                {
                    add(i+n,t,inf);
                    add(t,i+n,0);
                }else
                {
                    add(i+n,t,1);
                    add(t,i+n,0);
                }
            }
            if(i==1||i==n)
            {
                add(i,i+n,inf);
                add(i+n,i,0);
            }else
            {
                add(i,i+n,1);
                add(i+n,i,0);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(a[i]<=a[j]&&dp[j]==dp[i]+1)
                {
                    add(i+n,j,1);
                    add(j,i+n,0);
                }
            }
        }
        int ans=dinic();
        printf("%d\n",ans);
    }
}

上一篇:virsh命令文档


下一篇:http错误代码含义