题解 P3254 【圆桌问题】

圆桌问题从题目标签上是网络流24题，但是想了一下，再A掉之后又看了一题解，发现和我一样写贪心的童鞋好像没有与我思路相同的，所以我就来写个第一篇题解吧。 思路大致如下： 1、 将数据按要求输入并存储下来。 2、 对于每一个单位的每一个而言，每次都只坐没有同事，并且空座最多的桌子（桌子容量依次减少）。 3、 将落座的人所坐的桌号用桶排序的方法记录下来。 4、 所有单位处理完成后，按次序输出结果。 代码奉上，自取不谢。 ```cpp #include<cstdio> #include<cstring> //引入必要的头文件 using namespace std; int danwei[200]; struct zhuo//创建一个用于存储桌子信息的结构体数组 { int shu; int wei; }t[300]; int m,n; int vis[300];//记录每张桌子上是否有本单位的人 int res[200][300];//答案数组 inline int dfs(int num,int i)//处理每个单位代表落座的函数 { if(num==0) return 1;//代表全都落座则返回 int rong=0; int index=0; for(int j=1;j<=n;j++)//循环以找到桌子剩余座位的最大值 { if(t[j].shu==t[j].wei || vis[j]) continue;//如果桌子坐满或者单位有人坐过就找下一张桌子 if(rong<(t[j].wei-t[j].shu))//如果容量比最大容量大则更新最大容量和它的位置 { rong=(t[j].wei-t[j].shu); index=j; } } if(index==0) return 0;//容量为空则说明无法坐下，题目不成立 vis[index]=1;//落座，改变桌子的容量 t[index].shu++; res[i][index]++;//记录答案，表示第i号单位的第index章桌子上有人 int r=dfs(num-1,i);//看本单位下一个人能否落座 return r; } inline void sc()//输出答案函数 { printf("1\n"); for(int i=1;i<=m;i++) { int j=1; int num=0; for(;j<=n;j++) { if(res[i][j]==0) continue;//如果桌子上没人，就看下一张桌子 printf("%d",j);//有人就打印桌子号 if(++num!=danwei[i])printf(" "); else printf("\n"); } } } inline int A()//伪主函数（提高效率使用，执行时从这里执行） { scanf("%d %d",&m,&n);//输入m和n for(int i=1;i<=m;i++)//输入每个单位的人数 { scanf("%d",&danwei[i]); } for(int i=1;i<=n;i++)//输入每张桌子的位置数 { scanf("%d",&t[i].wei); } for(int i=1;i<=m;i++)//循环对于每一个单位人数去找座位 { int r=dfs(danwei[i],i);//调用处理落座的函数 if(r==0)//有人无法落座则不符合题目要求 { printf("%d\n",r); return 0; } memset(vis,0,sizeof(vis));//对于每一次运行清空桌子的访问记录 } sc();//调用输出函数 return 0;//函数结尾 } int B=A();//调用伪主函数 int main()//真的毫无内容的主函数 { return 0; //函数结尾 } ```