线性规划与网络流24题-圆桌问题
【问题分析】
二分图多重匹配问题，可以用最大流解决。
【建模方法】
建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。 2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。 3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
【建模分析】
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
【问题另解】
贪心，更好的方法其实是贪心。首先把所有单位和餐桌按人数从大到小排序，一种适当的贪心策略就是对于每个单位，所有人每次尽量去剩余容量较大的餐桌就坐。按照这种贪心策略，如果某时发现有人已经无法就坐，则无解。具体方法为用线段树维护餐桌的剩余容量，按人数从多到少安排每个单位的人员，每次安排就是把容量餐桌前k大的餐桌人数减1（k为该单位人数）。为保证线段树前k位时刻为前k大，要维护第k与第k+1,k+2,…人数与第k相等的位置，减少第k大时要减少尽量靠后的，这样才能保证单调。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Problem: 线性规划与网络流24题 #5 圆桌问题 | |
| * Author: Guo Jiabao | |
| * Time: 2009.6.27 12:59 | |
| * State: Solved | |
| * Memo: 网络最大流 二分图多重匹配 | |
| */ | |
| #include <iostream> | |
| #include <cstdio> | |
| #include <cstdlib> | |
| #include <cmath> | |
| #include <cstring> | |
| using namespace std; | |
| const int MAXN=150+270+3,MAXM=150*270*2+MAXN*2,INF=~0U>>1; | |
| struct edge | |
| { | |
| edge *next,*op; | |
| int t,c; | |
| }*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN]; | |
| int N,M,S,T,EC,Ans,Maxflow,Total; | |
| int Lv[MAXN],Stap[MAXN]; | |
| inline void addedge(int a,int b,int c) | |
| { | |
| ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; | |
| ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; | |
| V[a]->op = V[b]; V[b]->op = V[a]; | |
| } | |
| void init() | |
| { | |
| int i,j,c; | |
| freopen("table.in","r",stdin); | |
| freopen("table.out","w",stdout); | |
| scanf("%d%d",&M,&N); | |
| S=0; T=N+M+1; | |
| for (i=1;i<=M;i++) | |
| { | |
| scanf("%d",&c); | |
| Total += c; | |
| addedge(S,i,c); | |
| } | |
| for (i=1;i<=N;i++) | |
| { | |
| scanf("%d",&c); | |
| addedge(i+M,T,c); | |
| } | |
| for (i=1;i<=M;i++) | |
| for (j=N;j>=1;j--) | |
| addedge(i,j+M,1); | |
| } | |
| bool Dinic_Label() | |
| { | |
| int head,tail,i,j; | |
| Stap[head=tail=0]=S; | |
| memset(Lv,-1,sizeof(Lv)); | |
| Lv[S]=0; | |
| while (head<=tail) | |
| { | |
| i=Stap[head++]; | |
| for (edge *e=V[i];e;e=e->next) | |
| { | |
| j=e->t; | |
| if (e->c && Lv[j]==-1) | |
| { | |
| Lv[j] = Lv[i]+1; | |
| if (j==T) | |
| return true; | |
| Stap[++tail] = j; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| void Dinic_Augment() | |
| { | |
| int i,j,delta,Stop; | |
| for (i=S;i<=T;i++) | |
| P[i] = V[i]; | |
| Stap[Stop=1]=S; | |
| while (Stop) | |
| { | |
| i=Stap[Stop]; | |
| if (i!=T) | |
| { | |
| for (;P[i];P[i]=P[i]->next) | |
| if (P[i]->c && Lv[i] + 1 == Lv[j=P[i]->t]) | |
| break; | |
| if (P[i]) | |
| { | |
| Stap[++Stop] = j; | |
| Stae[Stop] = P[i]; | |
| } | |
| else | |
| Stop--,Lv[i]=-1; | |
| } | |
| else | |
| { | |
| delta = INF; | |
| for (i=Stop;i>=2;i--) | |
| if (Stae[i]->c < delta) | |
| delta = Stae[i]->c; | |
| Maxflow += delta; | |
| for (i=Stop;i>=2;i--) | |
| { | |
| Stae[i]->c -= delta; | |
| Stae[i]->op->c += delta; | |
| if (Stae[i]->c==0) | |
| Stop = i-1; | |
| } | |
| } | |
| } | |
| } | |
| void Dinic() | |
| { | |
| while (Dinic_Label()) | |
| Dinic_Augment(); | |
| } | |
| void print() | |
| { | |
| if (Total == Maxflow) | |
| { | |
| printf("1\n"); | |
| for (int i=1;i<=M;i++) | |
| { | |
| for (edge *e=V[i];e;e=e->next) | |
| if (e->c == 0 && e->t !=S) | |
| printf("%d ",e->t-M); | |
| putchar('\n'); | |
| } | |
| } | |
| else | |
| printf("0\n"); | |
| } | |
| int main() | |
| { | |
| init(); | |
| Dinic(); | |
| print(); | |
| return 0; | |
| } |
圆桌问题
问题描述: 假设有来自 n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri ,i =1,2,...,n。会议餐厅共有 m 张餐桌,每张餐桌可容纳ci (i =1,2,...,m)个代表就餐。为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法, 给出满足要求的代表就餐方案。
编程任务: 对于给定的代表数和餐桌数以及餐桌容量,编程计算满足要求的代表就餐方案。
́数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 m 和 n,m 表示单位数,n 表示餐桌数,1<=m
结果输出:
程序运行结束时,将代表就餐方案输出到文件 output.txt 中。如果问题有解,在文件第 1 行输出 1,否则输出 0。接下来的 m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案,只要输出 1 个方案。
输入文件示例
input.txt
4 5
4 5 3 5
3 5 2 6 4
输出文件示例
output.txt
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
上次修改时间 2017-02-03