比赛 HAOI2009 模拟试题3 评测结果 AWWAWWWAAW
题目名称 诸侯安置 最终得分 40
用户昵称 BYVoid 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2009-04-23 10:13:58
显示代码纯文本
/* 
 * Problem: HAOI2009 模拟3 empire
 * Author: Guo Jiabao
 * Time: 2009.4.23 10:12
 * State: Done
 * Memo: 二分图匹配计数 网络最大流 强连通分量
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1000,MOD=504,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
	edge *next,*op;
	int t,c;
	bool original;
}*V[MAXN],*P[MAXN],*Stae[MAXN];
int N,K,Ans,S,S0,T;
int Stop,Stap[MAXN],Lv[MAXN];
int Bel[MAXN],DFN[MAXN],Low[MAXN],Dindex,Bcnt,Ecnt[MAXN];
bool instack[MAXN];
void tarjan(int i)
{
	int j;
	DFN[i]=Low[i]=++Dindex;
	Stap[++Stop]=i; instack[i]=true;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!e->c) continue;
		if (!DFN[j])
		{
			tarjan(j);
			if (Low[j] < Low[i])
				Low[i] = Low[j];
		}
		else if (instack[j] && DFN[j] < Low[i])
			Low[i] = DFN[j];
	}
	if (Low[i] == DFN[i])
	{
		Bcnt++;
		do{
			j=Stap[Stop--];
			instack[j]=false;
			Bel[j]=Bcnt;
		}while (j!=i);
	}
}
void SCC()
{
	Bcnt=Dindex=Stop=0;
	for (int i=1;i<=N;i++)
		if (!Bel[i])
			tarjan(i);
}
bool Dinic_BFS()
{
	int i,j,head=0,tail=-1;
	memset(Lv,-1,sizeof(Lv));
	Lv[Stap[++tail]=S]=0;
	while (head<=tail)
	{
		i=Stap[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (Lv[j]==-1 && e->c)
			{
				Lv[j] = Lv[i] + 1;
				if (j==T)
					return true;
				Stap[++tail]=j;
			}
		}
	}
	return false;
}
void Dinic_Augment()
{
	int i,j,delta;
	for (i=S;i<=T;i++)
		P[i]=V[i];
	Stap[Stop=1]=S;
	while (Stop)
	{
		i=Stap[Stop];
		if (i!=T)
		{
			for (;P[i];P[i]=P[i]->next)
				if (P[i]->c && Lv[i] + 1 == Lv[j=P[i]->t])
					break;
			if (P[i])
			{
				Stap[++Stop]=j;
				Stae[Stop]=P[i];
			}
			else
			{
				Stop--;
				Lv[i]=-1;
			}
		}
		else
		{
			delta=INF;
			for (i=Stop;i>=2;i--)
				if (Stae[i]->c < delta)
					delta = Stae[i]->c;
			for (i=Stop;i>=2;i--)
			{
				Stae[i]->c -= delta;
				Stae[i]->op->c += delta;
				if (Stae[i]->c==0)
					Stop=i-1;
			}
		}
	}
}
void Dinic()
{
	while (Dinic_BFS())
		Dinic_Augment();
}
inline void addedge(int a,int b,int c,bool o)
{
	Ans++;
	edge e1={V[a],0,b,c,o},e2={V[b],0,a,0,false};
	V[a]=new edge(e1); V[b]=new edge(e2);
	V[a]->op=V[b]; V[b]->op=V[a];
	//printf("(%d,%d)\n",a,b-N);
}
void init()
{
	int i,j,P;
	freopen("empire.in","r",stdin);
	freopen("empire.out","w",stdout);
	scanf("%d%d",&N,&K);P=N;
	N=N+N-1;
	for (i=1;i<=P;i++)
	{
		for (j=P-i+1;j<=P+i-1;j++)
		{
			addedge(i,j+N,1,true);
			if (i<P)
				addedge(N-i+1,j+N,1,true);
		}
	}
	S=0;S0=N+N+1;T=N+N+2;
	for (i=1;i<=N;i++)
	{
		addedge(S0,i,1,false);
		addedge(i+N,T,1,false);
	}
	addedge(S,S0,K,false);
	Ans=0;
}
void GetEdge()
{
	int i,j,P;
	for (i=1;i<=N+N;i++)
	{
		P=0;
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (j==S0 || j==T) continue;
			if (Bel[i]==Bel[j] && e->c==0)
				Ecnt[Bel[i]]++;
		}
	}
}
void solve()
{
	Dinic();
	if (V[S]->c > 0)
		return;
	SCC();
	GetEdge();
	Ans=1;
	for (int i=1;i<=Bcnt;i++)
	{
		if (Ecnt[i])
		{
			Ans *= Ecnt[i];
			Ans %= MOD;
		}
	}
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}