圆桌问题(网络流24题)

题意

有n个单位，每个单位有一些人，有m张桌子，每张桌子可以坐一些人，每个单位的人不能坐一张桌子，输出方案。

1<=n<=150, 1<=m<=270。

题解

一开始把每个人都看成一个点，然后一个一个依次放进去，就是贪心（可这和网络流有什么关系呢），于是放弃了。去看题解，还真**可以贪心，需要一些排序。

然后网络流解法来了，把单位和桌子看成两部分，桌子与单位之间连边流量为1就可以保证条件，源点与单位之间连边流量为单位人数，汇点与桌子之间连边流量为桌子容量。

（我真蠢）

然后交了一波平常写的网络流结果最后一个点疯狂T，明明前面还都挺快，然后一看讨论很多都是最后一个点T，然后有的说要当前弧优化啥的。

（不想学）就去看了题解，看到一个dalao说这题不用拆点，弧优化，二分答案，xjb建图，是清流（疑问脸）。一看感觉没啥区别嘛，就只有在dfs里面一句 if(!rest) break;

结果加上直接原地起飞。

#include<bits/stdc++.h>
using namespace std;

const int maxn=506;
const int maxm=90006;
int n,m,tot;
int cnt=1,s,t,head[maxn];
struct edge{
  int x,y,val,next;
}e[maxm];

void add(int x,int y,int val){
  e[++cnt]=(edge){x,y,val,head[x]};
  head[x]=cnt;
}

int d[maxn];

bool bfs(){
  queue<int> q;
  memset(d,0,sizeof(d));
  q.push(s);d[s]=1;
  while(!q.empty()){
    int x=q.front();
    q.pop();
    for(int i=head[x];i;i=e[i].next){
      int y=e[i].y;
      if(e[i].val&&!d[y]){
        d[y]=d[x]+1;
        if(y==t) return true;
        q.push(y);
      }
    }
  }
  return false;
}

int dfs(int x,int flow){
  if(x==t) return flow;
  int rest=flow,k;
  for(int i=head[x];i;i=e[i].next){
    int y=e[i].y;
    if(e[i].val&&d[y]==d[x]+1){
      k=dfs(y,min(rest,e[i].val));
      e[i].val-=k;
      e[i^1].val+=k;
      rest-=k;
      if(!rest) break;
    }
  }
  return flow-rest;
}

int dinic(){
  int res=0;
  while(bfs()) res+=dfs(s,0x3f3f3f);
  return res;
}

int main(){
  scanf("%d%d",&n,&m);
  s=0;t=n+m+1;
  for(int i=1;i<=n;i++){
    int x;scanf("%d",&x);
    tot+=x;
    add(s,i,x);
    add(i,s,0);
    for(int j=n+1;j<=n+m;j++){
      add(i,j,1);
      add(j,i,0);
    }
  }
  for(int i=n+1;i<=n+m;i++){
    int x;scanf("%d",&x);
    add(i,t,x);
    add(t,i,0);
  }
  int ans=dinic();
  if(ans!=tot){printf("0");return 0;}
  printf("1
");
  for(int i=1;i<=n;i++){
    for(int j=head[i];j;j=e[j].next)
     if(!e[j].val) printf("%d ",e[j].y-n);
    putchar(10);
  }
}