【BZOJ3168】[Heoi2013]钙铁锌硒维生素

Description

银河队选手名单出来了！小林，作为特聘的营养师，将负责银河队选手参加宇宙比赛的饮食。众所周知，前往宇宙的某个星球，通常要花费好长好长的时间，人体情况在这之间会发生变化，因此，需要根据每天的情况搭配伙食，来保证营养。小林把人体需要的营养分成了n种，这些营养包括但不限于铁，钙。他准备了2套厨师机器人，一套厨师机器人有n个，每个厨师机器人只会做一道菜，这道菜一斤能提供第i种营养xi微克。想要吃这道菜的时候，只要输入一个数，就能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害，每个机器人还有防过量摄入药，只要输入一个数，就能生成一定剂量的药，吃了这些药，就能减少相当于食用对应数目的这道菜提供的营养。小林之所以准备2套厨师机器人，正是因为旅途漫漫，难以预计，也许某一个厨师机器人在途中坏掉，要是影响了银河队选手的身体，就不好了。因此，第2套厨师机器人被用来做第1套的备用。小林需要为每一个第1套厨师机器人选一个第2套厨师机器人作备份，使得当这个机器人坏掉时，用备份顶替，整套厨师机器人仍然能搭配出任何营养需求，而且，每个第2套厨师机器人只能当一个第1套厨师机器人的备份。

Input

第一行包含一个正整数n。

接下来n行，每行n个整数，表示第1套厨师机器人做的菜每一斤提供的每种营养。

再接下来n行，每行n个整数，表示第2套厨师机器人做的菜每一斤提供的每种营养。

1≤n≤300，所有出现的整数均非负，且不超过10,000。

Output

第一行是一个字符串，如果无法完成任务，输出“NIE”，否则输出“TAK”

并跟着n行，第i行表示第i个第1套机器人的备份是哪一个第2套机器人。

为了避免麻烦，如果有多种可能的答案，请给出字典序最小的那一组。

Sample Input

3
1 0 0
0 1 0
0 0 1
2 3 0
0 7 8
0 0 9

Sample Output

TAK
1
2
3

题解：要不是有大爷的题解我还真就不一定能看懂题意。。。

题目大意：给定一个

求出来C后，我们改变思路，将用边i->j表示B中j号机器人能替换A中i号机器人，然后就得到了一个二分图，而C^T正好是二分图的邻接矩阵，我们想求二分图的字典序最小的完美匹配。

一开始以为大爷做麻烦了，直接从后往前做一遍匈牙利算法就行，知道我看了Discuss。。。好吧还是要做两边，第一遍正常跑，第二遍贪心的选编号小的，并且要求后面的点不能影响前面的点。

这里依旧是做一下大爷博客的注释：

1.为什么是CA=B而不是AC=B？？？（我一开始也死活搞不懂）
因为每个机器人对应一个行向量，而我们想让A中的行向量对应B中另外一个行向量，这显然直接矩乘是不行的，但如果我们将A，B分别转置，就可以做到A中一个列向量对应B中另外一个列向量，然后就是A^TC=B^T（这里的C指的就是二分图的邻接矩阵），等价于C^TA=B

2.不影响前面的交错环是什么鬼？（或者你认为我说的也不是那么清楚？）

直接说方法吧：在第二遍DFS的时候记录一下当前是从那个点开始去寻找增广路的，也就意味着编号比这个点小的点我们都不能影响。所以我们看一下B中的机器人所对应的A中的机器人的编号，如果编号<起始点，就不能更改；如果编号=起始点，而我们已经向让起始点和其它点匹配了，这个点就已经被闲置出来了，就可以更改；如果编号>起始点，那么我们继续寻找增广路就行了。

#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#define mod 999911657using namespace std;const double eps=1e-6;typedef long long ll;int n,ans;ll A[310][610],B[310][310],C[310][310];int vis[310],from[310],to[310];ll pm(ll x,ll y){	ll z=1;	while(y)	{		if(y&1)	z=z*x%mod;		x=x*x%mod,y>>=1;	}	return z;}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int dfs1(int x){	for(int i=1;i<=n;i++)	{		if(C[i][x]&&!vis[i])		{			vis[i]=1;			if(!from[i]||dfs1(from[i]))			{				to[x]=i,from[i]=x;				return 1;			}		}	}	return 0;}int dfs2(int x,int y){	for(int i=1;i<=n;i++)	{		if(C[i][x]&&!vis[i])		{			vis[i]=1;			if(from[i]==y||(from[i]>y&&dfs2(from[i],y)))			{				from[i]=x,to[x]=i;				return 1;			}		}	}	return 0;}int main(){	n=rd();	int i,j,k;	for(i=1;i<=n;i++)	for(j=1;j<=n;j++)	A[i][j]=rd(),A[i][j+n]=(i==j);	for(i=1;i<=n;i++)	for(j=1;j<=n;j++)	B[i][j]=rd();	ll t;	for(i=1;i<=n;i++)	{		for(j=i;j<=n;j++)	if(A[j][i])		{			for(k=1;k<=2*n;k++)	swap(A[i][k],A[j][k]);			break;		}		t=pm(A[i][i],mod-2);		for(k=i;k<=2*n;k++)	A[i][k]=A[i][k]*t%mod;		for(j=1;j<=n;j++)	if(i!=j)		{			t=A[j][i];			for(k=1;k<=2*n;k++)	A[j][k]=(A[j][k]-t*A[i][k]%mod+mod)%mod;		}	}	for(i=1;i<=n;i++)	for(j=1;j<=n;j++)	for(k=1;k<=n;k++)	C[i][j]=(C[i][j]+B[i][k]*A[k][j+n])%mod;	for(i=1;i<=n;i++)	{		memset(vis,0,sizeof(vis));		ans+=dfs1(i);	}	if(ans<n)	{		printf("NIE");		return 0;	}	printf("TAK\n");	for(i=1;i<=n;i++)	{		memset(vis,0,sizeof(vis));		dfs2(i,i);	}	for(i=1;i<=n;i++)	printf("%d\n",to[i]);	return 0;}

【BZOJ3168】[Heoi2013]钙铁锌硒维生素高斯消元求矩阵的逆+匈牙利算法

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ3168】[Heoi2013]钙铁锌硒维生素 高斯消元求矩阵的逆+匈牙利算法