BZOJ 1433 [ZJOI2009]假期的宿舍

默默地断更好久，总算还是决定厚着脸皮先来水一篇续上。。。

orz Chester_king帮我发现初始化问题。。。

#include<cstdio>#include<vector>#include<queue>#include<cstring>#define INF 1e8using namespace std;struct Edge{	int from,to,cap,flow;};vector <Edge> edges;vector <int> G[105];int T,s,t,n,m,a[51],b[51],d[105],v[105],cur[105];void add(int x,int y,int cap,int flow){	edges.push_back((Edge){x,y,cap,0});	G[x].push_back(m);	++m;	edges.push_back((Edge){y,x,0,0});	G[y].push_back(m);	++m;}int BFS(int s,int t){	memset(d,0,sizeof(d));	memset(v,0,sizeof(v));	d[s]=0;	v[s]=1;	queue<int>dui;	dui.push(s);	while(!dui.empty())	{		int p=dui.front();		dui.pop();		for(int i=0;i<G[p].size();++i)		{			Edge e=edges[G[p][i]];			if(!v[e.to]&&e.cap>e.flow)			{				v[e.to]=1;				d[e.to]=d[p]+1;				dui.push(e.to);			}		}	}	return v[t];}int min(int a,int b){return a<b?a:b;}int DFS(int x,int a){	if(x==t||a==0)		return a;	int f,flow=0;	for(int &i=cur[x];i<G[x].size();++i)	{		Edge &e=edges[G[x][i]];		if(d[e.to]==d[x]+1&&(f=DFS(e.to,min(a,e.cap-e.flow))>0))		{			e.flow+=f;			a-=f;			edges[G[x][i]^1].flow-=f;			flow+=f;			if(a==0)				break;		}	}	return flow;}int maxflow(int s,int t){	int flow=0;	while(BFS(s,t))	{		memset(cur,0,sizeof(cur));		flow+=DFS(s,INF);	}	return flow;}int main(){	scanf("%d",&T);	while(T--)	{		edges.clear();		scanf("%d",&n);		int i,j,p,tmp=0;		for(i=0;i<=104;++i)			G[i].clear();		m=0;		s=0,t=104;		for(i=1;i<=n;++i)		{			scanf("%d",&a[i]);			if(a[i])				add(i+n,t,1,0);	//这个人有床，连一条边		}		for(i=1;i<=n;++i)		{			scanf("%d",&b[i]);			if((a[i]&&!b[i])||!a[i]) //这个人不是在校生或者是回家的在校生就连一条边，他要住在学校里			{				++tmp;				add(s,i,1,0);			}		}		for(i=1;i<=n;++i)			for(j=1;j<=n;++j)			{				scanf("%d",&p);				if((p&&a[j])||i==j) //i和j认识并且j有床或者是他自己连一条边					add(i,j+n,1,0);			}		if(maxflow(s,t)==tmp)			PRintf("^_^/n");		else			printf("T_T/n");	}	return 0;}
写给自己：考试爆炸心态很崩？不行那就不是我了。赶紧开始搞事，做上进的好学生。毕竟爆炸了代表进步空间很大（逃）