链接：https://www.luogu.com.cn/problem/P6775
题目描述：有\(m\)道菜，和\(n\)种原材料，每个原材料有一个质量\(d_{i}\),有\(\sum_{i=1}^{n}{d_{i}}=m\times k\)(m为正整数)，每次在\(1-2\)道菜中选一部分满足质量总和为\(k\)，求一组合法方案。
题解：考场上想了\(3h\)会了\(70\),结果\(m>n-1\)判错\(WA\)成\(55\)。
假如我们已经选定好了一种方案\(T\)，那么我们可以考虑如何判定合法性，我们可以建出网络流模型，然后两边跑最大流，判是否满流。
但是我们会发现，若现在的判定方案为\(T\),在跑网络流的时候，对于\(d_{i}>=k\)，我们可以将它流掉，那么它一定可以被单独做为\(1\)道菜流，所以我们可以将它流掉。
考虑流掉后\(m\)的范围，若\(m>=n-1\)，由于有\(d_{i}<k\)，那么\(\sum_{i=1}^{n}d_{i}<=k\times n\),又有\(\sum_{i=1}^{n}d_{i}=k\times m\)，则\(m<=n-1\)，所以对于\(m>=n-1\)可以归纳为\(m=n-1\)。
那么考虑如何构造一组\(m=n-1\)的方案，可以如下构造方案：
先处理\(n\)个数，将最小的元素与最大的元素匹配从而消去最小的元素，这样就消去了一个数，然后对于剩下的数反复该过程。
考虑如何证明，令\(d\)从小到大排序后为\(D\),则最小的数为\(D_{1}\),最大的数为\(D_{n}\),那么因\(\sum_{i=1}^{n}D_{i}=(n-1)\times k\),则若\(D_{1}+D_{n}<k\),那么有\(\sum_{i=1}^{n}D_{i}<=D_{1}+(n-1)\times D_{n}<=(n-1)\times (D_{1}+D_{n})<(n-1)\times k\)，则矛盾，即\(D_{1}+D_{n}>=k\)，可以构造出一组方案。
那么对于\(m=n-2\)的情况，我们发现无法归纳解决，那么仔细观察可以发现有解时\(m=n-2\)的解中一定会有两个不连通的\(m=n-1\)。
考虑如何证明。由于拆时将其拆为连通图，那么这些图都有\(m>=n-1\),那么若对于一个点数为\(N\)，边数为\(M\)的连通图，若\(M \times k=\sum_{i=1}^{n}d_{i}\)，则即可归纳为\(m>=n-1\)的问题，一定存在解。反之，则会无法恰好选完，则无解。
即\(M \times k=\sum_{i=1}^{N}d_{i}\)为连通图有解的充要条件。
那么考虑我们\(m=n-2\)的解是若干个连通图，每个图需满足上述条件，在这些图会存在一些带环图与树，那么将带环图与树合并，合并出的新连通图仍满足这个条件，那么合并会更优，在合并完后会合并成两颗无法合并的树，所以有解时一定会有两个不连通的\(m=n-1\)。
那么我们可以构造一颗树，另外一颗树就满足条件，即需构造\((N-1) \times k=\sum_{i=1}^{N}d_{i}\)，这个可化为\(k=\sum_{i=1}^{N}(k-d_{i})\),将\(k-d_{i}\)看作元素可以背包，转移时可用\(bitset\)优化转移。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
sum=sum*10+c-'0',c=getchar();
return sum;
}
struct node
{
int num,d;
bool operator < (const node &a)const
{
return d<a.d;
}
};
node point[501],tong[501];
int T,n,m,k,cnt,length,maxer,maxn;
bool used[501];
bitset<4980001>dp[501];
int main()
{
bool op;
T=read();
while (T--)
{
n=read(),m=read(),k=read();
for (int i=1;i<=n;++i)
point[i].num=i,point[i].d=read();
if (m>=n-1)
{
cnt=0;
for (int i=1;i<=n;++i)
while (point[i].d>=k&&cnt<m-n+1)
cnt++,point[i].d-=k,printf("%d %d\n",point[i].num,k);
for (int t=1;t<=n;++t)
{
sort(point+t,point+n+1);
if (point[t].d==0)
continue;
if (point[t].d==k)
{
printf("%d %d\n",point[t].num,k);
continue;
}
printf("%d %d %d %d\n",point[t].num,point[t].d,point[n].num,k-point[t].d);
point[n].d-=(k-point[t].d);
}
}
else
{
for (int i=1;i<=n;++i)
used[i]=0;
for (int i=0;i<=n;++i)
dp[i].reset();
dp[0][(n-2)*k]=1;
int s,ps,tmp;
op=0;
for (int i=1;i<=n;++i)
{
if (k-point[i].d>=0)
dp[i]=dp[i-1]|(dp[i-1]<<(k-point[i].d));
else
dp[i]=dp[i-1]|(dp[i-1]>>(point[i].d-k));
if (dp[i][k+(n-2)*k])
{
op=1;
used[i]=1,s=k+(n-2)*k-(k-point[i].d),ps=i;
while (ps!=0)
{
tmp=ps;
for (int j=0;j<=tmp-1;++j)
if (dp[j][s])
{
ps=j;
break;
}
used[ps]=1;
s=s-(k-point[ps].d);
}
break;
}
}
if (op)
{
length=0;
for (int i=1;i<=n;++i)
if (used[i])
tong[++length]=point[i];
for (int t=1;t<=length;++t)
{
sort(tong+t,tong+length+1);
if (tong[t].d==0)
continue;
printf("%d %d %d %d\n",tong[t].num,tong[t].d,tong[length].num,k-tong[t].d);
tong[length].d-=(k-tong[t].d);
}
length=0;
for (int i=1;i<=n;++i)
if (!used[i])
tong[++length]=point[i];
for (int t=1;t<=length;++t)
{
sort(tong+t,tong+length+1);
if (tong[t].d==0)
continue;
printf("%d %d %d %d\n",tong[t].num,tong[t].d,tong[length].num,k-tong[t].d);
tong[length].d-=(k-tong[t].d);
}
}
else
puts("-1");
}
}
return 0;
}