hkr04‘s blogs

题解

建立超级源超级汇，建立源点->国际单位->圆桌->汇点的网络。其中，源点连边容量为$r_i$（INF也可以，反正限制主要是后面），国际单位连边容量为1，圆桌连边容量为$c_i$。跑出最大流即可得到最大匹配，与人数总数相比较即可知道是否有合法方案。方案统计只需对每个单位查询有哪些边的流量不为0即可。

有一个小技巧是，先连国际单位->圆桌，后面统计时，查验边是否流量不为0的顺序就和存边时相等。由于同时存正反边（编号从2开始），第$i$个单位和第$j$个圆桌之间的边的编号即为$((i-1)\times n+j)\times 2$。

代码

#include <cstdio>
const int maxn=500;
const int maxm=1e5;
const int INF=0x3f3f3f3f;
int cur[maxn],head[maxn],to[maxm<<1],nxt[maxm<<1],val[maxm<<1];
int tot=1;
int c[maxn],r[maxn];
int s,t,n,m;
int dep[maxn];
struct  Queue
{
	int a[maxn];
	int l,r;
	Queue() {l=1,r=0;}
	void push(int x) {a[++r]=x;}
	void pop() {l++;}
	int front() {return a[l];}
	bool empty() {return l>r;}
}q;

int min(int x,int y) {return x<y?x:y;}
void add(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=w;
}
bool bfs()
{
	for (int i=1;i<=n+m+1;i++)
		dep[i]=INF;
	q=Queue();
	dep[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if (val[i]&&dep[v]>dep[u]+1)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]<INF;
}
int dfs(int u,int minf)
{
	if (u==t)
		return minf;
	int used=0;
	for (int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if (val[i]&&dep[v]==dep[u]+1)
		{
			int flow=dfs(v, min(minf-used, val[i]));
			if (flow)
			{
				used+=flow;
				val[i]-=flow;
				val[i^1]+=flow;
				if (used==minf)
					break;
			}
		}
	}
	return used;
}
int main()
{
	scanf("%d%d",&m,&n);
	int sum=0;
	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]);
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
			add(i, m+j, 1),add(m+j, i, 0);

	s=0,t=n+m+1;
	for (int i=1;i<=m;i++)
		add(s, i, r[i]),add(i, s, 0);
	for (int i=1;i<=n;i++)
		add(m+i, t, c[i]),add(t, m+i, 0);

	int cnt=0;
	while(bfs())
	{
		for (int i=0;i<=n+m;i++)
			cur[i]=head[i];
		cnt+=dfs(s, INF);
	}
	if (cnt<sum)
		printf("0\n");
	else
	{
		printf("1\n");
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=n;j++)
				if (!val[((i-1)*n+j)<<1])
					printf("%d ",j);
			putchar('\n');
		}
	}
	return 0;
}