记录编号	142982	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]男生女生	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.206 s
提交时间	2014-12-12 11:10:18	内存使用	48.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const LL MOD=19921228;
const int SIZEN=2510,SIZEn=55,INF=0x7fffffff/2;
class Edge{
public:
	int from,to,cap,flow;
	void print(void){cout<<from<<" "<<to<<" "<<cap<<" "<<flow<<endl;}
};
int N,S,T;
vector<Edge> edges;
vector<int> c[SIZEN];
bool vis[SIZEN]={0};
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int depth[SIZEN];
int cur[SIZEN];
bool BFS(void){
	memset(vis,0,sizeof(vis));
	static queue<int> Q;
	while(!Q.empty()) Q.pop();
	Q.push(S);vis[S]=true;depth[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			Edge &e=edges[c[x][i]];
			if(e.flow>=e.cap) continue;
			if(!vis[e.to]){
				vis[e.to]=true;
				depth[e.to]=depth[x]+1;
				Q.push(e.to);
			}
		}
	}
	return vis[T];
}
int DFS(int x,int a){
	if(x==T||!a) return a;
	int ans=0;
	for(int &i=cur[x];i<c[x].size();i++){
		Edge &e=edges[c[x][i]];
		if(depth[x]+1==depth[e.to]){
			int cf=DFS(e.to,min(a,e.cap-e.flow));
			if(cf){
				ans+=cf;a-=cf;
				e.flow+=cf;edges[c[x][i]^1].flow-=cf;
			}
			if(!a) break;
		}
	}
	if(!ans) depth[x]=-1;
	return ans;
}
int Dinic(void){
	int ans=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		ans+=DFS(S,INF);
	}
	return ans;
}
int n,m,K;
int A,B;
LL C[SIZEN][SIZEN];
bool mate[SIZEn][SIZEn]={0};
void calc_C(int n){
	memset(C,0,sizeof(C));
	for(int i=0;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
}
LL f[SIZEn][SIZEn];
void DP(void){
	calc_C(n*n);
	for(int i=1;i<=A;i++){
		for(int j=1;j<=B;j++){
			f[i][j]=C[i*j][K];
			for(int i1=1;i1<=i;i1++){
				for(int j1=1;j1<=j;j1++){
					if(i1==i&&j1==j) continue;
					LL now=(C[i][i1]*C[j][j1])%MOD;
					now=(now*f[i1][j1])%MOD;
					f[i][j]=(f[i][j]+MOD-now)%MOD;
				}
			}
		}
	}
}
void work(void){
	int all=Dinic()/N;
	BFS();
	A=0;
	for(int i=1;i<=n;i++) if(!vis[i]) A++;
	B=all-A;
	A=n-A,B=n-B;
	DP();
	printf("%d %d\n",A,B);
	printf("%lld\n",f[A][B]);
}
void init(void){
	scanf("%d%d",&n,&K);
	N=2*n+1,S=0,T=N;
	scanf("%d",&m);
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		mate[a][b]=true;
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mate[i][j]^=1;
	//现在我们试图在mate规定的图中求最大独立集
	//即求出最小支配集,其中试图让x部选出的点数最少
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			if(mate[i][j]) addedge(i,j+n,INF);
	}
	for(int i=1;i<=n;i++){
		addedge(S,i,N+1);
		addedge(i+n,T,N);
	}
}
int main(){
	freopen("boygirl.in","r",stdin);
	freopen("boygirl.out","w",stdout);
	init();
	work();
	return 0;
}