圆桌问题

摘要

复习 Dinic~

假设有来自 m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri (i =1,2,……,m)。

会议餐厅共有 n 张餐桌,每张餐桌可容纳 ci (i =1,2,……,n) 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,给出满足要求的代表就餐方案。输出方案

简单的网络流建模

建边 含义
从源点向第 i 个单位的点连边,表示第 i 个单位有 个人
第 i 个单位到第 j 个餐桌最多 1 个人
第 j 个餐桌最多有 个人
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+6,INF=0x3f3f3f3f;

struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v),add_path(t,f,0);}

int s,t;
int d[N];
queue<int> q;
bool bfs(){memset(d,0,sizeof(d));
    d[s]=1,q.push(s);
    while(q.size()){int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(!w||d[v])continue;
            d[v]=d[u]+1,q.push(v);
        }
    }
    return d[t];
}
int dinic(int u,int flow){if(u==t)return flow;
    int rest=flow;
    for(int i=h[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(!w||d[v]!=d[u]+1)continue;
        int k=dinic(v,min(rest,w));
        if(k)e[i].v-=k,e[i^1].v+=k,rest-=k;
        else d[v]=0;
    }
    return flow-rest;
}

int m,n,sum;
int r[N],c[N];
int main(){scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)scanf("%d",&r[i]),sum+=r[i];
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    s=0,t=m+n+1;
    for(int i=1;i<=m;i++){add_flow(s,i,r[i]);
        for(int j=1;j<=n;j++)add_flow(i,m+j,1);
    }
    for(int i=1;i<=n;i++)add_flow(m+i,t,c[i]);
    int maxflow=0;
    while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;
    if(maxflow<sum)return puts("0"),0;
    else puts("1");
    for(int u=1;u<=m;u++){for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
            if(w)continue;
            printf("%d",v-m);
        }
        puts("");
    }
    return 0;
}

  转载请注明: Sshwy's Blog 圆桌问题

 上一篇
Aria2 使用指北 Aria2 使用指北
摘要 aria2 对于普通用户可能并没有那么友好,不过在进行配置后,它将是真正的开源免费下载利器!对于那些不了解 aria2 的同学,笔者就本文章介绍一下 aria2 在 linux 下的使用 被遗弃的 Windows?aria2 并不是
2019.04.13
下一篇 
NOI2016 优秀的拆分 NOI2016 优秀的拆分
摘要 人生第二道黑题~ 如果一个字符串可以被拆分为 AABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成
2019.04.10
  目录