Topic

Title Link: https://www.luogu.com.cn/problem/P6775

General idea of the topic

n n n raw materials, No i i i have d i d_i di ， Nos, m m m dishes are required k k k raw materials, and each dish can only use two materials at most.

The construction scheme is required to meet the conditions.

1 ≤ n ≤ 500 , n − 2 ≤ m ≤ 5000 , 1 ≤ k ≤ 5000 , ( ∑ i = 1 n d i ) = m × k 1\leq n\leq 500,n-2\leq m\leq 5000,1\leq k\leq 5000,(\sum_{i=1}^nd_i)=m\times k 1≤n≤500,n−2≤m≤5000,1≤k≤5000,(∑i=1n​di​)=m×k

Problem solving ideas

Well, I didn't think at all during the online game last year. It's time for me to have a shame calendar before the snow (although this problem is still very difficult)

First, we notice a special condition n − 2 ≤ m n-2\leq m n − 2 ≤ m, it seems that there is no idea, but look at the data range n − 1 = m n-1=m n − 1=m and n − 1 ≤ m n-1\leq m n − 1 ≤ m is divided into two parts.

First consider n − 1 = m n-1=m If n − 1=m, there are more raw materials than dishes, then we must have d m i n < k d_{min}<k dmin < K and d m i n + d m a x > k ( n ≠ 2 ) d_{min}+d_{max}>k(n\neq 2) dmin​+dmax​>k(n​=2).

Well, so we take the least one raw material and the most one raw material every time to make a dish, so we are still satisfied n − 1 = m n-1=m n − 1=m.

Then consider n ≤ m n\leq m In the case of n ≤ m, it is not difficult to find that there must be d m a x ≥ k d_{max}\geq k dmax ≥ k, so we just take the most to make a dish, so why not n − 1 , m − 1 n-1,m-1 n − 1,m − 1 or m − 1 m-1 m − 1 becomes n − 1 = m n-1=m n − 1=m.

Then n − 2 = m n-2=m The practice of n − 2=m is the core difficulty of this problem.

I have seen an interesting proof in the solution of the Luogu problem. We can regard the raw materials as one point and the two raw materials used in dishes as one edge, so because m = n − 2 m=n-2 m=n − 2, so this graph must be disconnected, then it will be divided into at least two trees.

Found that for trees m = n − 1 m=n-1 m=n − 1, so it's actually equivalent to that we're going to m = n − 2 m=n-2 The case of m=n − 2 is divided into two m = n − 1 m=n-1 m=n − 1.

And because m = n − 1 m=n-1 m=n − 1 must have a solution, so we just need to consider how to divide it.

It's equivalent to finding a set of raw materials S S S makes
∑ i ∈ S d i = ( ∣ S ∣ − 1 ) k ⇒ ∑ i ∈ S ( d i − k ) = − k \sum_{i\in S}d_i=(|S|-1)k\Rightarrow \sum_{i\in S}(d_i-k)=-k i∈S∑​di​=(∣S∣−1)k⇒i∈S∑​(di​−k)=−k

Then directly d p dp The complexity of dp is O ( T n 2 k ) O(Tn^2k) O(Tn2k), plus one b i t s e t bitset bitset optimization is O ( T n 2 k w ) O(T\frac{n^2k}{w}) O(Twn2k), you can pass this question

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
const int N=510,S=5e6+10,W=2500000;
struct node{
	int w,id;
}d[N];
struct cnode{
	int a,A,b,B;
}v[N*10];
int T,n,m,k,tot;
bool vis[N];
bitset<S>f[N];
vector<node> u;
bool cmp(node x,node y)
{return x.w<y.w;}
void Add(int a,int A,int b=0,int B=0)
{v[++tot]=(cnode){a,A,b,B};return;}
void solve(int m,vector<node> &d){
	int n=d.size();tot=0;
	while(m&&m>=n){
		sort(d.begin(),d.end(),cmp);
		Add(d[n-1].id,k);
		d[n-1].w-=k;m--;
		if(!d[n-1].w)d.pop_back(),n--;
	}
	if(m==n-1){
		while(m){
			sort(d.begin(),d.end(),cmp);swap(d[0],d[n-1]);
			Add(d[n-1].id,d[n-1].w,d[0].id,k-d[n-1].w);
			d[0].w-=k-d[n-1].w;d.pop_back();n--;m--;
			if(!d[0].w)swap(d[0],d[n-1]),d.pop_back(),n--;
		}
	}
	for(int i=1;i<=tot;i++){
		if(v[i].b)printf("%d %d %d %d\n",v[i].a,v[i].A,v[i].b,v[i].B);
		else printf("%d %d\n",v[i].a,v[i].A);
	}
	u.clear();return;
}
int main()
{
	scanf("%d",&T);
	f[0][W]=1;
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&d[i].w),d[i].id=i;
		if(m==n-2){
			for(int i=1;i<=n;i++){
				int tmp=d[i].w-k;
				if(tmp>=0){
					f[i]=f[i-1];
					f[i]|=(f[i-1]<<tmp);
				}
				else{
					f[i]=f[i-1];
					f[i]|=(f[i-1]>>(-tmp));
				}
			}
			if(!f[n][W-k])puts("-1");
			else{
				memset(vis,0,sizeof(vis));
				for(int i=n,z=W-k;i>=1;i--){
					int tmp=d[i].w-k;
					if(f[i-1][z-tmp])
						u.push_back(d[i]),vis[i]=1,z-=tmp;
				}
				solve(u.size()-1,u);
				for(int i=1;i<=n;i++)
					if(!vis[i])u.push_back(d[i]);
				solve(u.size()-1,u);
			}
		}
		else{
			for(int i=1;i<=n;i++)
				u.push_back(d[i]);
			solve(m,u);
		}
	}
	return 0;
}