CF1242C. Sum Balance

题目描述

k组数，每组ni个，数互不相同

把每组数中的一个移到其他组（或者不移动），使得最终每组数的个数不变且总和相等

k<=15,ni<=5000

题解

最终的移动关系一定为若干个环

枚举每个环的起点，找到一个数补上去使得和等于平均值

因为互不相同，所以出边（找到的数）唯一

判断是否能成环，并且把对应的选择方案记下

预处理的时间为O(k*∑ni)

最后O(3^n)dp即可

code

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;

struct type{
    int s,x,y;
} a[75001];
int p[16]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
int b[16][5001];
int c[16];
int d[32768][16][2]; //d[][1][1] is special
int d2[16][2];
bool bz[16];
bool f[32768];
int g[32768];
int ans[16][2];
int D[16];
int n,I,J,i,j,k,l,len,S,s,L,tot;
long long Sum[16];
long long sum;

bool cmp(type a,type b)
{
    return a.s<b.s;
}

int get(long long t)
{
    int l=1,r=len,mid;

    while (l<r)
    {
        mid=(l+r)/2;

        if (a[mid].s<t)
        l=mid+1;
        else
        r=mid;
    }

    if (a[l].s==t)
    return l;
    return -1;
}

int main()
{
//  freopen("c.in","r",stdin);

    scanf("%d",&n);L=p[n]*2-1;
    fo(i,1,n)
    {
        scanf("%d",&c[i]);
        fo(j,1,c[i])
        scanf("%d",&b[i][j]),a[++len]={b[i][j],i,j},sum+=b[i][j],Sum[i]+=b[i][j];
    }

    if (sum%n)
    {
        printf("No\n");
        return 0;
    }
    sum/=n;

    sort(a+1,a+len+1,cmp);

    fo(I,1,n)
    {
        fo(J,1,c[I])
        {
            memset(bz,0,sizeof(bz));

            S=p[I];

            tot=1;
            d2[1][0]=I;
            d2[1][1]=b[I][J];

            j=I;
            s=b[I][J];

            l=get(sum-(Sum[j]-s));

            while (!bz[j])
            {
                bz[j]=1;

                if (l==-1 || bz[a[l].x])
                break;

                j=a[l].x;
                s=a[l].s;
                S|=p[j];

                ++tot;
                d2[tot][0]=j;
                d2[tot][1]=l;

                l=get(sum-(Sum[j]-s));
            }

            if (l!=-1 && a[l].x==I && a[l].y==J)
            {
                f[S]=1;
                fo(j,1,tot)
                {
                    d[S][j][0]=d2[j][0];
                    d[S][j][1]=d2[j][1];
                }
            }
        }
    }

    fo(i,1,L)
    {
        if (f[i])
        g[i]=i;
        else
        {
            for (j=(i-1)&i; j; j=(j-1)&i)
            if (f[j] && g[i^j])
            {
                g[i]=j;
                break;
            }
        }
    }

    if (g[L])
    {
        for (j=L; j; j^=g[j])
        {
            tot=0;
            fo(i,1,n)
            if (g[j]&p[i])
            ++tot;

            ans[d[g[j]][1][0]][0]=d[g[j]][tot][0];
            ans[d[g[j]][1][0]][1]=d[g[j]][1][1];
            fo(i,2,tot)
            {
                ans[d[g[j]][i][0]][0]=d[g[j]][i-1][0];
                ans[d[g[j]][i][0]][1]=a[d[g[j]][i][1]].s;
            }
        }

        printf("Yes\n");
        fo(i,1,n)
        printf("%d %d\n",ans[i][1],ans[i][0]);
    }
    else
    printf("No\n");
}