Loading...

洛谷P3254 圆桌问题

check评论:0 条 remove_red_eye浏览量:332 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-14

网络流水题qwq

首先想一想同一个公司每个桌子只能一个人意味着每个公司向每个桌子连一条流量为$1$的边

然后建立超级源点和汇点,超级源点向每个公司连公司人数,每个桌子向超级汇点连桌子人数

然后就是裸的最大流了

只要最大流跑出来和总人数一样就行了,输出路径的话直接枚举公司的满流就可以了

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,cnt,per[300],zhu[300];
int vis[400],dis[400],head[400],ans;
struct edge
{
    int next,to,flow;
}e[800];
void add(int u,int v,int flow)
{
    cnt++;
    e[cnt]=(edge){head[u],v,flow};
    head[u]=cnt;
}
int bfs()
{
    queue<int> q;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].flow>0)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int expe)
{
    if(u==t||!expe)
    {
        return expe;
    }
    int flow=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].flow>0&&dis[v]==dis[u]+1)
        {
            int tmp=dfs(v,min(e[i].flow,expe));
            if(!tmp)
            {
                continue;
            }
            expe-=tmp;
            flow+=tmp;
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            if(!expe)
            {
                break;
            }
        }
    }
    return flow;
}
int main()
{
    cin>>n>>m;
    cnt=1;
    s=0,t=(n<<1)+1;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&per[i]);
        for(int j=1;j<=m;j++)
        {
            add(i,j+n,1);
            add(j+n,i,0);
        }
        add(s,i,per[i]);
        add(i,s,0);
        sum+=per[i];
    }
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&zhu[j]);
        add(j+n,t,zhu[j]);
        add(t,j+n,0);
    }
    while(bfs())
    {
        ans+=dfs(s,0x3f3f3f3f);
    }
    if(ans==sum)
    {
        cout<<"1"<<endl;
        for(int i=1;i<=n;i++)
        {
            for(int j=head[i];j;j=e[j].next)
            {
                int v=e[j].to;
                if(v>n&&v<=n+m&&!e[j].flow)
                {
                    printf("%d ",v-n);
                }
            }
            printf("\n");
        }
    }
    else
    {
        cout<<"0";
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名