列表

详情


NC17411. room

描述

Nowcoder University has 4n students and n dormitories ( Four students per dormitory). Students numbered from 1 to 4n.

And in the first year, the i-th dormitory 's students are (x1[i],x2[i],x3[i],x4[i]), now in the second year, Students need to decide who to live with.

In the second year, you get n tables such as (y1,y2,y3,y4) denote these four students want to live together.

Now you need to decide which dormitory everyone lives in to minimize the number of students who change dormitory.

输入描述

The first line has one integer n.

Then there are n lines, each line has four integers (x1,x2,x3,x4) denote these four students live together in the first year

Then there are n lines, each line has four integers (y1,y2,y3,y4) denote these four students want to live together in the second year

输出描述

Output the least number of students need to change dormitory.

示例1

输入:

2
1 2 3 4
5 6 7 8
4 6 7 8
1 2 3 5

输出:

2

说明:

Just swap 4 and 5

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 996K, 提交时间: 2018-08-07 18:21:30

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<set>
using namespace std;
const int inf=~0u>>2,N=210,M=30000;
int tmp,ans;
int u[M],v[M],c[M],co[M],nxt[M],t=1,S,T,l,r,q[M],g[N],f[N],d[N];bool in[N];
int nn,pa[N][4],pb[N][4];
void add(int x,int y,int z,int zo)
{
	u[++t]=x;v[t]=y;c[t]=z;co[t]=zo;nxt[t]=g[x];g[x]=t;
	u[++t]=y;v[t]=x;c[t]=0;co[t]=-zo;nxt[t]=g[y];g[y]=t;
}
bool spfa()
{
	int x,i;
	for(i=1;i<=T;i++)d[i]=inf,in[i]=0;
	d[S]=0;in[S]=1;l=r=M>>1;q[l]=S;
	while(l<=r)
	{
		x=q[l++];
		if(x==T)continue;
		for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]<d[v[i]])
		{
			d[v[i]]=co[i]+d[x];f[v[i]]=i;
			if(!in[v[i]])
			{
				in[v[i]]=1;
				if(d[v[i]]<d[q[l]])q[--l]=v[i];else q[++r]=v[i];
			}
		}
		in[x]=0;
	}
	return d[T]<inf;
}
int main(void)
{
	int i,j,k,p;set<int>ff;
	scanf("%d",&nn);
	for(i=1;i<=nn;i++)for(j=0;j<=3;j++)scanf("%d",&pa[i][j]);
	for(i=1;i<=nn;i++)for(j=0;j<=3;j++)scanf("%d",&pb[i][j]);
	S=0;T=nn+nn+1;
	for(i=1;i<=nn;i++){add(S,i,1,0);add(i+nn,T,1,0);}
	for(i=1;i<=nn;i++)for(j=1;j<=nn;j++)
	{
		ff.clear();for(k=0;k<=3;k++)ff.insert(pb[j][k]);
		p=0;for(k=0;k<=3;k++)p+=(ff.find(pa[i][k])==ff.end());
		add(i,j+nn,1,p);
	}
	while(spfa())
	{
		for(tmp=inf,i=T;i!=S;i=u[f[i]])if(tmp>c[f[i]])tmp=c[f[i]];
		for(ans+=d[i=T]*tmp;i!=S;i=u[f[i]])c[f[i]]-=tmp,c[f[i]^1]+=tmp;
	}
	printf("%d",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 608K, 提交时间: 2018-08-08 23:14:05

#include<bits/stdc++.h>
using namespace std;
#define rep(i,boy) for(int i=1;i<=boy;i++)
#define clr(a,b) memset(a,b,sizeof(a))
const int N=105,meizi=-0x7fffffff;
int n,w[N][N],cx[N],cy[N],girl[N],x[N][5];
bool usex[N],usey[N];
bool find(int x)
{
	usex[x]=true;
	rep(i,n)
	{
		if(!usey[i]&&cx[x]+cy[i]==w[x][i])
		{
			usey[i]=true;
			if(girl[i]==0||find(girl[i]))
			{
				girl[i]=x;
				return true;
			}
		}
	}
	return false;
}
int km()
{
	rep(i,n)while(true)
	{
		int d=meizi;
		clr(usex,false);clr(usey,false);
		if(find(i))break;
		rep(j,n)if(usex[j])rep(k,n)if(!usey[k])d=min(d,cx[j]+cy[k]-w[j][k]);
		rep(j,n)
		{
			if(usex[j])cx[j]-=d;
			if(usey[j])cy[j]+=d;
		}
	}
	int ans=0;
	rep(i,n)ans+=w[girl[i]][i];
	return -ans;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	clr(cx,0);clr(cy,0);
	cin>>n;
	rep(i,n)rep(j,4)cin>>x[i][j];
	rep(i,n)
	{
		map<int,bool>mmp;
		rep(j,4)
		{
			int y;cin>>y;
			mmp[y]=true;
		}
		rep(k,n)
		{
			int cnt=0;
			rep(j,4)if(mmp[x[k][j]])cnt++;
			w[k][i]=cnt-4;
			cx[k]=max(cx[k],cnt-4);
		}
	}
	cout<<km()<<endl;
} 

上一题