2012-A3-0026
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<set>
#include<functional>
using namespace std;
//using namespace rel_ops;
typedef unsigned u32;
const double eps = 1e-8;
struct real{
double z;
real(){};real(double x):z(x){}
};
real operator *(const real& a,const real& b){
return real(a.z*b.z);
}
real operator /(const real& a,const real& b){
return real(a.z/b.z);
}
bool operator == (const real&a ,const real& b){
return fabs(a.z/b.z-1.0)<eps;
}
bool operator < (const real &a,const real &b){
return a.z/b.z+eps<1.0;
}
typedef pair<real,u32> eT;
eT operator +(const eT& a,const eT& b){
return eT(a.first*b.first,a.second+b.second);
}
eT operator -(const eT&a,const eT& b){
return eT(a.first/b.first,a.second-b.second);
}
u32 pts[5120];
real pos[10][5120];
u32 cmpk;
struct cmp{
bool operator()(u32 a,u32 b){
return pos[cmpk][b]<pos[cmpk][a]||pos[cmpk][a]==pos[cmpk][b]&&pts[a]>pts[b];
}
};
const u32 N =100;
eT e[10][N];
u32 m1[10],m2[N];
eT KuhnMunkras(u32 m,u32 n, eT e[][N], u32 * m1, u32 * m2) {
static u32 s[N + 1], t[N],p, q, i, j, k;
static eT l1[N],l2[N];
for(i = 0; i < m; i++)
for (l1[i] = eT(real(0),0) ,j = 0; j < n; j++)
if(l1[i]<e[i][j])l1[i]=e[i][j];
for(i=0;i<n;l2[i++] = eT(real(1.0),0u));
memset(m1,0xff,m*sizeof(u32));
memset(m2,0xff,n*sizeof(u32));
for (i =0;i<m;i++) {
memset(t,0xff,n*sizeof(u32));
for (s[p=q=0]=i;p<=q&&!~m1[i];p++)
for (k=s[p],j=0;j<n&&!~m1[i];j++)
if (l1[k]+l2[j]==e[k][j]&&!~t[j]) {
s[++q]=m2[j];t[j] = k;
if (!~s[q])
for(p=j;~p;j=p){
m2[j]=k=t[j];
p= m1[k];
m1[k] = j;
}
}
if (!~m1[i]) {
eT p(real(1e10),0);--i;
for (k = 0; k<= q;k++)
for (j = 0;j< n; j++)
if (!~t[j] && l1[s[k]] + l2[j] < p+ e[s[k]][j])
p = l1[s[k]] + l2[j] - e[s[k]][j];
for (j = 0; j < n; j++)
if(~t[j])l2[j] = l2[j]+p;
for (k = 0; k <= q; k++)l1[s[k]] = l1[s[k]]- p;
}
}
eT ret(real(1.0),0u);
for (i = 0; i < m; i++)
ret = ret + e[i][m1[i]];
return ret;
}
priority_queue<u32,vector<u32> , cmp > useful[10];
int main(){
for(u32 m,n;scanf("%u%u",&n,&m)==2;){
for(u32 i=0;i<m;++i)scanf("%u",pts+i);
for(u32 i=0;i<n;++i){
cmpk=i;
for(u32 j=0;j<m;++j){
scanf("%lf",&pos[i][j].z);
useful[i].push(j);
if(useful[i].size()>n)useful[i].pop();
}
}
for(u32 i=0,j;i<n;++i){
for(j=0;j<m&&pos[i][j]<eps;++j);
if(j==m){
sort(pts,pts+m,greater<u32>());
printf("%u\n",accumulate(pts,pts+n,0u));
n = 0; break;
}
}
if(!n)continue;
set<u32> temp;
for(u32 i=0;i<n;++i)
for(;useful[i].size();useful[i].pop())
temp.insert(useful[i].top());
m =0;
for(__typeof(temp.end()) it =temp.begin();
it!=temp.end();++it,++m){
pts[m] = pts[*it];
for(u32 j=0;j<n;++j)
e[j][m] = eT(real(pos[j][m]=pos[j][*it]),pts[m]);
}
printf("%u\n",KuhnMunkras(n,m,e,m1,m2).second);
}
return 0;
}
}}}#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<set>
#include<functional>
using namespace std;
//using namespace rel_ops;
typedef unsigned u32;
const double eps = 1e-8;
struct real{
double z;
real(){};real(double x):z(x){}
};
real operator *(const real& a,const real& b){
return real(a.z*b.z);
}
real operator /(const real& a,const real& b){
return real(a.z/b.z);
}
bool operator == (const real&a ,const real& b){
return fabs(a.z/b.z-1.0)<eps;
}
bool operator < (const real &a,const real &b){
return a.z/b.z+eps<1.0;
}
typedef pair<real,u32> eT;
eT operator +(const eT& a,const eT& b){
return eT(a.first*b.first,a.second+b.second);
}
eT operator -(const eT&a,const eT& b){
return eT(a.first/b.first,a.second-b.second);
}
u32 pts[5120];
real pos[10][5120];
u32 cmpk;
struct cmp{
bool operator()(u32 a,u32 b){
return pos[cmpk][b]<pos[cmpk][a]||pos[cmpk][a]==pos[cmpk][b]&&pts[a]>pts[b];
}
};
const u32 N =100;
eT e[10][N];
u32 m1[10],m2[N];
eT KuhnMunkras(u32 m,u32 n, eT e[][N], u32 * m1, u32 * m2) {
static u32 s[N + 1], t[N],p, q, i, j, k;
static eT l1[N],l2[N];
for(i = 0; i < m; i++)
for (l1[i] = eT(real(0),0) ,j = 0; j < n; j++)
if(l1[i]<e[i][j])l1[i]=e[i][j];
for(i=0;i<n;l2[i++] = eT(real(1.0),0u));
memset(m1,0xff,m*sizeof(u32));
memset(m2,0xff,n*sizeof(u32));
for (i =0;i<m;i++) {
memset(t,0xff,n*sizeof(u32));
for (s[p=q=0]=i;p<=q&&!~m1[i];p++)
for (k=s[p],j=0;j<n&&!~m1[i];j++)
if (l1[k]+l2[j]==e[k][j]&&!~t[j]) {
s[++q]=m2[j];t[j] = k;
if (!~s[q])
for(p=j;~p;j=p){
m2[j]=k=t[j];
p= m1[k];
m1[k] = j;
}
}
if (!~m1[i]) {
eT p(real(1e10),0);--i;
for (k = 0; k<= q;k++)
for (j = 0;j< n; j++)
if (!~t[j] && l1[s[k]] + l2[j] < p+ e[s[k]][j])
p = l1[s[k]] + l2[j] - e[s[k]][j];
for (j = 0; j < n; j++)
if(~t[j])l2[j] = l2[j]+p;
for (k = 0; k <= q; k++)l1[s[k]] = l1[s[k]]- p;
}
}
eT ret(real(1.0),0u);
for (i = 0; i < m; i++)
ret = ret + e[i][m1[i]];
return ret;
}
priority_queue<u32,vector<u32> , cmp > useful[10];
int main(){
for(u32 m,n;scanf("%u%u",&n,&m)==2;){
for(u32 i=0;i<m;++i)scanf("%u",pts+i);
for(u32 i=0;i<n;++i){
cmpk=i;
for(u32 j=0;j<m;++j){
scanf("%lf",&pos[i][j].z);
useful[i].push(j);
if(useful[i].size()>n)useful[i].pop();
}
}
for(u32 i=0,j;i<n;++i){
for(j=0;j<m&&pos[i][j]<eps;++j);
if(j==m){
sort(pts,pts+m,greater<u32>());
printf("%u\n",accumulate(pts,pts+n,0u));
n = 0; break;
}
}
if(!n)continue;
set<u32> temp;
for(u32 i=0;i<n;++i)
for(;useful[i].size();useful[i].pop())
temp.insert(useful[i].top());
m =0;
for(__typeof(temp.end()) it =temp.begin();
it!=temp.end();++it,++m){
pts[m] = pts[*it];
for(u32 j=0;j<n;++j)
e[j][m] = eT(real(pos[j][m]=pos[j][*it]),pts[m]);
}
printf("%u\n",KuhnMunkras(n,m,e,m1,m2).second);
}
return 0;
}