P3254 圆桌问题(最大流板子,求二分图多重最大匹配的值)

 

题目描述

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

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

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

对于给定的代表数和餐桌数以及餐桌容量,编程计算满足要求的代表就餐方案。

输入格式

第1 行有2 个正整数m 和n,m 表示单位数,n 表示餐桌数,1<=m<=150, 1<=n<=270。

第2 行有m 个正整数,分别表示每个单位的代表数。

第3 行有n 个正整数,分别表示每个餐桌的容量。

输出格式

如果问题有解,第1 行输出1,否则输出0。接下来的m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案,只要输出1 个方案。

输入输出样例

输入 #1
4 5
4 5 3 5
3 5 2 6 4
输出 #1
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5


理论基础看这里 最大流理论
(1)二分图多重最大匹配:
在原图上建立源点S和汇点T,S向每个X点连一条容量为该X点L值的边,每个Y点向T连一条容量为该Y点L值的边,原来二分图中各边在新的网络中仍存在,容量为1(若该边可以使用多次则容量大于1),求该网络的最大流,就是该二分图多重最大匹配的值。
  1 #include<bits/stdc++.h> //求该网络的最大流,就是该二分图多重最大匹配的值。
  2 #define N 520
  3 using namespace std;
  4 typedef struct
  5 {
  6     int v;
  7     long long flow;
  8 }ss;
  9 
 10 ss edg[N*N];
 11 vector<int>edges[N];
 12 int now_edges=0;
 13 long long fl[N][N]={0};
 14 
 15 void addedge(int u,int v,long long flow)
 16 {
 17     fl[u][v]+=flow;
 18     edges[u].push_back(now_edges);
 19     edg[now_edges++]=(ss){v,flow};
 20     edges[v].push_back(now_edges);
 21     edg[now_edges++]=(ss){u,0}; //反向边真正的意义是使原边流量减少,而不是真的有反向流量
 22 }
 23 
 24 int dis[N],S,T;
 25 bool bfs() //寻找从源点到汇点的增广路
 26 {
 27     memset(dis,0,sizeof(dis));
 28     queue<int>q;
 29     q.push(S);
 30     dis[S]=1;
 31     
 32     while(!q.empty())
 33     {
 34         int now=q.front();
 35         q.pop();
 36         int Size=edges[now].size();
 37         
 38         for(int i=0;i<Size;i++)
 39         {
 40             ss e=edg[edges[now][i]];
 41             if(e.flow>0&&dis[e.v]==0)
 42             {
 43                 dis[e.v]=dis[now]+1;
 44                 q.push(e.v);
 45             }
 46         }
 47     }    
 48     if(dis[T]==0)return 0;
 49     return 1;
 50     
 51 }
 52 int current[N];//记录当前点遍历到了那一条边
 53 long long dfs(int now,long long maxflow)//w代表当前点   , maxflow为搜索到该点时的可能的最大流量 
 54 {
 55     if(now==T)return maxflow;//如果搜索到汇点,就可以返回了 
 56     int Size=edges[now].size();//Size为now号点所连边的数量 
 57     for(int i=current[now];i<Size;i++)//因为某一个点可能会被多次遍历,但是该点的某些边可能已经被增广过了,所以这些边应该没必要搜索 
 58     {                                //于是我们对每一个点记录一个current代表这个点已经遍历到了哪一条边 
 59     
 60         current[now]=i;    //记录current 
 61         ss &e=edg[edges[now][i]];  
 62         
 63         if(e.flow>0&&dis[e.v]==dis[now]+1)    //如果改边有容量并且改边的终点和now点满足层数关系 
 64         {                                        //这里的层数关系是因为dfs增广要按一层一层的来增广,因为这样可以高效率的找到增广路 
 65             long long Flow=dfs(e.v,min(maxflow,e.flow)); //往下dfs 
 66             
 67             if(Flow)  //如果dfs结果有流量,就说明找到了增广路 
 68             {
 69                 fl[now][e.v]-=Flow;  //这个是题目需要的东西,方便输出答案用的 
 70                 fl[e.v][now]+=Flow; //同上 
 71                 
 72                 e.flow-=Flow;  //正向边容量减少 
 73                 edg[edges[now][i]^1].flow+=Flow;//反向边容量增加 
 74                 return Flow;//递归返回 
 75             }
 76         }
 77     }
 78     return 0;//没有增广路就返回0 
 79 }
 80 
 81 long long dinic()
 82 {
 83     long long ans=0,flow;
 84     while(bfs())
 85     {
 86         memset(current,0,sizeof(current));
 87         while(flow=dfs(S,LLONG_MAX/2))ans+=flow;//从源点开始初始最大流量是无穷
 88     }
 89     return ans;
 90 }
 91 
 92 int main()
 93 {
 94     int m,n;
 95     long long sum=0;
 96     int present[N],desk[N];
 97     scanf("%d %d",&m,&n);
 98     for(int i=1;i<=m;i++)scanf("%d",&present[i]),sum+=present[i];
 99     for(int i=1;i<=n;i++)scanf("%d",&desk[i]);
100     
101     S=n+m+1;
102     T=n+m+2;
103 
104     for(int i=1;i<=m;i++)addedge(S,i,present[i]);
105     for(int i=1;i<=n;i++)addedge(i+m,T,desk[i]);
106 
107     for(int i=1;i<=m;i++)
108     for(int j=1;j<=n;j++)
109     addedge(i,j+m,1);
110     
111     long long ans=dinic();
112     
113     if(sum==ans)
114     {
115         printf("1\n");
116         for(int i=1;i<=m;i++)
117         {
118             for(int j=1;j<=n;j++)
119             if(fl[j+m][i])printf("%d ",j);
120             printf("\n");
121         }
122     }
123     else
124     printf("0\n");
125     return 0;
126     
127 }

 

上一篇:克鲁斯卡尔算法与公交问题


下一篇:单源最短路(手写堆+位运算优化+卡常+O2 = Luogu排名最后一页...)