「WC2016」挑战NPC - 带花树

题目大意

    小N最近在研究NP完全问题，小O看小N研究得热火朝天，便给他出了一道这样的题目：
    有$n$个球，用整数$1$到$n$编号。还有$m$个筐子，用整数$1$到$m$编号。
    每个筐子最多能装$3$个球。
    每个球只能放进特定的筐子中。具体有$e$个条件，第$i$个条件用两个整数$v_i$和$u_i$描述，表示编号为$v_i$的球可以放进编号为$u_i$的筐子中。
    每个球都必须放进一个筐子中。如果一个筐子内有不超过$1$个球，那么我们称这样的筐子为半空的。
    求半空的筐子最多有多少个，以及在最优方案中，每个球分别放在哪个筐子中。
    小N看到题目后瞬间没了思路，站在旁边看热闹的小I嘿嘿一笑：“水题！”
    然后三言两语道出了一个多项式算法。
    小N瞬间就惊呆了，三秒钟后他回过神来一拍桌子：
    “不对！这个问题显然是NP完全问题，你算法肯定有错！”
    小I浅笑：“所以，等我领图灵奖吧!”
    小O只会出题不会做题，所以找到了你——请你对这个问题进行探究，并写一个程序解决此题。

---

题目分析

本题很无聊，本来带花树除了模板题是没什么用的，然而出一道题强行只能让带花树做。若不信你看，如果把筐子能装的球改成$4$就真的是NPC问题了。

直接讲建图方法：将筐拆成三个点，若一个球能够放到一个筐中，就与对应的筐的三个点分别连边，再将筐的三个点连起来成为一个三元环。答案即为最大匹配-球的个数。

为什么这样是对的呢？先考虑第一问的答案：若筐只装了$1$个球，最大匹配为$2$，对答案的贡献为$1$，若筐装了$2$个球，最大匹配为$2$，对答案的贡献为$0$，若筐装了$3$个球，最大匹配为$3$，对答案的贡献为$0$。
再来看第二问的输出方案，如果我们求最大匹配的时候先让球与筐匹配，后让筐与筐匹配，就可以使得球全部被匹配，否则可能会有球未被匹配，输出的时候处理一下匹配边即可。

如果要求判断是否有解的话，需要先写一个二分图多重匹配。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=605;

int n1,n2,N,m,father[maxn],vst[maxn],match[maxn],pre[maxn],Type[maxn];
vector<int>edges[maxn];
queue<int>Q;

void AddEdge(int x,int y) {
	edges[x].push_back(y);
	edges[y].push_back(x);
}

int LCA(int x,int y) {
	static int times=0;
	times++;
	x=father[x],y=father[y]; //已知环位置
	while(vst[x]!=times) {
		if(x) {
			vst[x]=times;
			x=father[pre[match[x]]];
		}
		swap(x,y);
	}
	return x;
}

void blossom(int x,int y,int lca) {
	while(father[x]!=lca) {
		pre[x]=y;
		y=match[x];
		if(Type[y]==1) {
			Type[y]=0;
			Q.push(y);
		}
		father[x]=father[y]=father[lca];
		x=pre[y];
	}
}

int Augument(int s) {
	for(int i=1; i<=N; i++)father[i]=i;
	memset(Type,-1,sizeof(Type));
	Q=queue<int>();
	Type[s]=0;
	Q.push(s); //仅入队o型点
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		for(int Next:edges[Now]) {
			if(Type[Next]==-1) {
				pre[Next]=Now;
				Type[Next]=1; //标记为i型点
				if(!match[Next]) {
					for(int to=Next,from=Now; to; from=pre[to]) {
						match[to]=from;
						swap(match[from],to);
					}
					return true;
				}
				Type[match[Next]]=0;
				Q.push(match[Next]);
			} else if(Type[Next]==0&&father[Now]!=father[Next]) {
				int lca=LCA(Now,Next);
				blossom(Now,Next,lca);
				blossom(Next,Now,lca);
			}
		}
	}
	return false;
}

int t,ans=0;

int id(int x,int y) {
	return (y-1)*n2+x;
}

void Clear() {
	for(int i=1; i<=N; i++)edges[i].clear();
	memset(match,0,sizeof(match));
	ans=0; //!!!
}

int main() {
	t=Get_Int();
	while(t--) {
		Clear();
		n1=Get_Int();
		n2=Get_Int();
		m=Get_Int();
		for(int i=1; i<=m; i++) {
			int x=Get_Int()+3*n2,y=Get_Int();
			AddEdge(x,id(y,1));
			AddEdge(x,id(y,2));
			AddEdge(x,id(y,3));
		}
		for(int i=1; i<=n2; i++) {
			AddEdge(id(i,1),id(i,2));
			AddEdge(id(i,2),id(i,3));
			AddEdge(id(i,1),id(i,3));
		}
		N=n1+3*n2;
		for(int i=N; i>=1; i--)
			if(!match[i])ans+=Augument(i);
		printf("%d\n",ans-n1);
		for(int i=3*n2+1; i<=N; i++)printf("%d ",match[i]%n2==0?n2:match[i]%n2);
		putchar('\n');
	}
	return 0;
}