Luogu

UOJ

分析

考虑把每个筐子拆成三个点，三个点间互相连边，然后每个球向能放的筐子拆成的三个点连边。

考虑这张图的一个最大匹配：如果某个筐子匹配了 $0$ 个球，那么会贡献 $1$ 个匹配；如果匹配了 $1$ 个球，那么会贡献 $2$ 个匹配；如果匹配了 $2$ 或 $3$ 个球，那么会贡献 $2$ 或 $3$ 个匹配。

也就是说，半空的筐子贡献的匹配数恰为匹配的球数加 $1$。

于是我们只需要求出整张图的最大匹配，然后减去 $n$ 即为答案。为了保证输出的方案正确，我们需要先匹配球。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=600+10;

int n,m,e;
vector<int> E[N];

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int lnk[N],pre[N],vis[N],vist[N],tim=0;
queue<int> Q;
int LCA(int u,int v) {
    ++tim,u=find(u),v=find(v);
    while (vist[u]!=tim) {
        vist[u]=tim,u=find(pre[lnk[u]]);
        if (v) swap(u,v);
    }
    return u;
}
void blossom(int u,int v,int t) {
    while (find(u)!=t) {
        pre[u]=v,v=lnk[u];
        if (vis[v]==2) vis[v]=1,Q.push(v);
        if (u==f[u]) f[u]=t;
        if (v==f[v]) f[v]=t;
        u=pre[v];
    }
}
bool bfs(int s) {
    while (!Q.empty()) Q.pop();
    for (int i=1;i<=n+m+m+m;++i) f[i]=i,vis[i]=pre[i]=0;
    Q.push(s),vis[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int v:E[u]) {
            if (find(u)==find(v)||vis[v]==2) continue;
            if (!vis[v]) {
                vis[v]=2,pre[v]=u;
                if (!lnk[v]) {
                    for (int x=v,y;x;x=y)
                        y=lnk[pre[x]],lnk[x]=pre[x],lnk[pre[x]]=x;
                    return 1;
                }
                vis[lnk[v]]=1,Q.push(lnk[v]);
            } else {
                int t=LCA(u,v); blossom(u,v,t),blossom(v,u,t);
            }
        }
    }
    return 0;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),e=read();
        for (int i=1;i<=e;++i) {
            int u=read(),v=read();
            E[u].emplace_back(v+n),E[v+n].emplace_back(u);
            E[u].emplace_back(v+n+m),E[v+n+m].emplace_back(u);
            E[u].emplace_back(v+n+m+m),E[v+n+m+m].emplace_back(u);
        }
        for (int i=1;i<=m;++i) {
            E[i+n].emplace_back(i+n+m),E[i+n+m].emplace_back(i+n);
            E[i+n].emplace_back(i+n+m+m),E[i+n+m+m].emplace_back(i+n);
            E[i+n+m].emplace_back(i+n+m+m),E[i+n+m+m].emplace_back(i+n+m);
        }
        memset(lnk,0,sizeof(lnk)); int ans=0;
        for (int i=1;i<=n+m+m+m;++i) if (!lnk[i]) ans+=bfs(i);
        printf("%d\n",ans-n);
        for (int i=1;i<=n;++i) printf("%d%c",(lnk[i]-n-1)%m+1," \n"[i==n]);

        for (int i=1;i<=n+m+m+m;++i) E[i].clear();
    }
    return 0;
}