bzoj4405: [wc2016]挑战NPC
学了一发带花树，表示scy的视频还是nb ——>前往caioj ORZ我们的红太阳（首页找视频）
然而这题更是好题。
把一个筐拆成一个三角形相互建边，然后把可以的球和这三个点建边，假如这个筐中的两个点匹配了，说明出现了一个半空筐，而每个球都会匹配到，那么答案就是匹配数减球数
一个小细节，要先让球去匹配，不然保证不了球都匹配到。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,m; struct node { int x,y,next; }a[210000];int len,last[11000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int fa[11000]; int findfa(int x) { if(fa[x]==x)return x; fa[x]=findfa(fa[x]);return fa[x]; } void unit(int x,int y) { int fx=findfa(x),fy=findfa(y); if(fx!=fy)fa[fx]=fy; } int match[11000],pre[11000],mark[11000]; int head,tail,list[11000]; int ts,vis[11000]; int LCA(int x,int y) { ts++; while(x!=0) { x=findfa(x); vis[x]=ts; x=pre[match[x]]; } while(y!=0) { y=findfa(y);if(vis[y]==ts)return y; vis[y]=ts; y=pre[match[y]]; } } void group(int x,int r) { while(x!=r) { int y=match[x],z=pre[y]; if(findfa(z)!=r)pre[z]=y; if(mark[y]==2) list[++tail]=y, mark[y]=1; if(mark[z]==2) list[++tail]=z, mark[z]=1; unit(x,y);unit(y,z); x=z; } } bool findniu(int s) { for(int i=1;i<=n+3*m;i++)fa[i]=i; memset(pre,0,sizeof(pre)); memset(mark,0,sizeof(mark)); head=1;tail=1;list[1]=s;mark[s]=1; while(head<=tail) { int x=list[head];head++; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(match[x]==y)continue; if(findfa(x)==findfa(y))continue; if(mark[y]==2)continue; if(mark[y]==0) { if(match[y]==0) { int p1=y,p2=x; while(p1!=0&&p2!=0) { int tt=match[p2]; match[p1]=p2;match[p2]=p1; p1=tt;p2=pre[p1]; } return true; } else { pre[y]=x; list[++tail]=match[y]; mark[match[y]]=1; mark[y]=2; } } else if(mark[y]==1) { int r=LCA(x,y); if(findfa(x)!=r)pre[x]=y; if(findfa(y)!=r)pre[y]=x; group(x,r);group(y,r); } } } return false; } int main() { int T_T; scanf("%d",&T_T); while(T_T--) { int E,x,y; scanf("%d%d%d",&n,&m,&E); //1~n ball n+1~n+m*3 base len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { ins(n+(i-1)*3+1,n+(i-1)*3+2); ins(n+(i-1)*3+2,n+(i-1)*3+1); ins(n+(i-1)*3+2,n+(i-1)*3+3); ins(n+(i-1)*3+3,n+(i-1)*3+2); ins(n+(i-1)*3+3,n+(i-1)*3+1); ins(n+(i-1)*3+1,n+(i-1)*3+3); } while(E--) { scanf("%d%d",&x,&y); ins(x,n+(y-1)*3+1);ins(n+(y-1)*3+1,x); ins(x,n+(y-1)*3+2);ins(n+(y-1)*3+2,x); ins(x,n+(y-1)*3+3);ins(n+(y-1)*3+3,x); } int ans=0; ts=0;memset(vis,0,sizeof(vis)); memset(match,0,sizeof(match)); for(int i=1;i<=n+3*m;i++) if(match[i]==0) if(findniu(i)==true)ans++; printf("%d ",ans-n); } return 0; }