正文

BZOJ3168: [Heoi2013]钙铁锌硒维生素

IP云
IP云V管理员/1 阅读
10/29
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

设$A^TC=B^T$，这样$C_{ij}$表示$B_j$的线性表出需要$A_i$，那么$B_j$可以替换$A_i$，根据$C=(A^T)^{-1}B^T$求出$C$。要求字典序最小完美匹配，先求任意完美匹配，然后从小到大尽可能把匹配改小，用类似匈牙利的方法找“增广路”。注意倒着跑是不行的，因为小的有可能影响到较小的，除非有其他限制。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300;
typedef ll arr[N][N];
arr s,t,e,c;
const int p=1e9+9;
int n,z[N],f[N];
ll wop(ll t,ll k){
for(ll s=1;;k>>=1){
if(k&1)s=s*t%p;
if(k<2)return s;
t=t*t%p;
}
}
bool dfs1(int i){
for(int j=0;j<n;++j)
if(c[i][j]&&!z[j]++&&(!~f[j]||dfs1(f[j])))
return&(f[j]=i);
return 0;
}
bool dfs2(int i,int k){
for(int j=0;j<n;++j)
if(c[i][j]&&!z[j]++&&(f[j]==k||f[j]>k&&dfs2(f[j],k)))
return&(f[j]=i);
return 0;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%lld",s[j]+i);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%lld",t[j]+i);
for(int i=0;i<n;++i)
e[i][i]=1;
for(int i=0;i<n;++i){
for(int j=i;j<n;++j)
if(s[j][i]){
for(int k=0;k<n;++k){
swap(s[j][k],s[i][k]);
swap(e[j][k],e[i][k]);
}
break;
}
ll v=wop(s[i][i],p-2);
for(int k=0;k<n;++k){
(s[i][k]*=v)%=p;
(e[i][k]*=v)%=p;
}
for(int j=0;j<n;++j){
if(j==i)continue;
v=(p-s[j][i])%p;
for(int k=0;k<n;++k){
(s[j][k]+=v*s[i][k])%=p;
(e[j][k]+=v*e[i][k])%=p;
}
}
}
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)
(c[i][k]+=e[i][j]*t[j][k])%=p;
memset(f,-1,sizeof f);
for(int i=0;i<n;++i){
memset(z,0,sizeof z);
if(!dfs1(i))
return!~puts("NIE");
}
for(int i=0;i<n;++i){
memset(z,0,sizeof z);
dfs2(i,i);
}
puts("TAK");
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(f[j]==i)printf("%d\n",j+1);
}