大致题意： 有(n)个球和(m)个筐，每个球可以放入某些筐中，且每个筐最多放(3)个球。现让你把所有球都放入筐中，问最多有多少个筐有不超过一个球。
前言
刚学带花树就来做这道题，不得不说实在是太妙了，根本想不到。。。
拆点
考虑我们把一个筐拆成三个点，然后在这三个点中两两连边，分别讨论一个筐中放不同数量球的情况：
- 不放球：此时对答案贡献为(1)，且一个筐拆成的三个点可以形成一个匹配。
- 放(1)个球：此时对答案贡献为(1)，且三个点中剩余的两个还可以形成一个匹配，共计两个匹配。
- 放(2)个球：此时对答案贡献为(0)，形成了两个匹配。
- 放(3)个球：此时对答案贡献为(0)，形成了三个匹配。
整理一下即可发现一个巧妙的规律：一个筐的贡献=形成匹配数-放的球数。
由于所有球都要放入筐中，因此放的球数之和就是(n)。
那么我们只要最大化形成匹配数之和，也就是求一般图最大匹配，则上带花树即可。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
#define M 300
#define P 1000
#define E 30000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,et,ee,lnk[P+5];struct edge {int to,nxt;}e[2*(3*E+3*M)+5];
class FlowerMatchTree//带花树模板
{
private:
int s[P+5],l[P+5],c[P+5],vis[P+5];queue<int> q;
int f[P+5];I int fa(CI x) {return f[x]?f[x]=fa(f[x]):x;}
I int LCA(RI x,RI y)
{
static int ti=0;++ti,x=fa(x),y=fa(y);
W(vis[x]^ti) vis[x]=ti,x=fa(l[s[x]]),y&&(x^=y^=x^=y);return x;
}
I void Blossom(RI x,RI y,CI p)
{
W(fa(x)^p) l[x]=y,y=s[x],!f[x]&&(f[x]=p),
!f[y]&&(f[y]=p),c[y]==2&&(q.push(y),c[y]=1),x=l[y];
}
I bool Match(CI x)//BFS
{
RI i;for(i=1;i<=n+3*m;++i) l[i]=c[i]=f[i]=0;W(!q.empty()) q.pop();
RI k,p;q.push(x),c[x]=1;W(!q.empty()) for(i=lnk[k=q.front()],q.pop();i;i=e[i].nxt)
{
if(fa(k)==fa(e[i].to)||c[e[i].to]==2) continue;
if(!c[e[i].to])
{
if(c[e[i].to]=2,l[e[i].to]=k,!s[e[i].to])
{for(k=e[i].to;k;k=p) p=s[l[k]],s[k]=l[k],s[l[k]]=k;return 1;}
c[s[e[i].to]]=1,q.push(s[e[i].to]);continue;
}
p=LCA(k,e[i].to),Blossom(k,e[i].to,p),Blossom(e[i].to,k,p);
}return 0;
}
public:
I int operator [] (CI x) {return s[x];}
I int GetAns()//求一般图最大匹配
{
RI i,t=0;for(i=1;i<=n+3*m;++i) s[i]=0;
for(i=1;i<=n+3*m;++i) !s[i]&&Match(i)&&++t;return t;
}
}T;
int main()
{
RI Tt,i,x,y;scanf("%d",&Tt);W(Tt--)
{
#define P(i,j) (n+3*((i)-1)+(j))//拆点
for(scanf("%d%d%d",&n,&m,&et),ee=0,i=1;i<=n+3*m;++i) lnk[i]=0;//清空
for(i=1;i<=et;++i) scanf("%d%d",&x,&y),add(x,P(y,1)),//向筐拆成的三个点连边
add(P(y,1),x),add(x,P(y,2)),add(P(y,2),x),add(x,P(y,3)),add(P(y,3),x);
for(i=1;i<=m;++i) add(P(i,1),P(i,2)),add(P(i,2),P(i,1)),//一个筐拆成的点间两两连边
add(P(i,1),P(i,3)),add(P(i,3),P(i,1)),add(P(i,2),P(i,3)),add(P(i,3),P(i,2));
for(printf("%d
",T.GetAns()-n),i=1;i<=n;++i) printf("%d%c",(T[i]-n+2)/3,"
"[i==n]);//输出答案
}return 0;
}