/ Randle /

记录详情

Wrong Answer

/in/foo.cc: In function 'int main()':
/in/foo.cc:182:15: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
       if((1<<j-1)&k)love[i][j]=1<<j-1;
              ~^~
/in/foo.cc:182:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
       if((1<<j-1)&k)love[i][j]=1<<j-1;
                                   ~^~
# 状态 耗时 内存占用
#1 Wrong Answer 5ms 4.25 MiB
#2 Wrong Answer 5ms 4.215 MiB
#3 Wrong Answer 6ms 4.211 MiB
#4 Wrong Answer 5ms 4.207 MiB
#5 Wrong Answer 7ms 4.215 MiB
#6 Accepted 32ms 4.223 MiB
#7 Accepted 62ms 4.25 MiB
#8 Wrong Answer 148ms 4.207 MiB
#9 Accepted 186ms 4.215 MiB
#10 Accepted 200ms 4.234 MiB

代码

/*
#include<bits/stdc++.h>
const int maxn=1e6; 
inline const void read(int &a)
{
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
int n,d=0;
int point[maxn],to[maxn],next[maxn],exboy[maxn],exgirl[maxn];
int boy[maxn],girl[maxn];
bool usedgirl[maxn],usedboy[maxn]; 
inline const bool found(int p)
{
	int side=point[p];
	while(side)
	{
		if(!usedgirl[to[side]])
		{
			usedgirl[to[side]]=true;
			if(!girl[to[side]]||found(girl[to[side]]))
			{
				boy[p]=to[side];
				girl[to[side]]=p;
				return true;
			}
		}
		side=next[side];
	}
	return false;
}
inline const void add(int a,int b)
{
	if(next[1]==14)
	{
		int k=0;
		k++;
	}
	next[++d]=point[a];
	point[a]=d;
	to[d]=b;
}
int main()
{
	//freopen("num10.in","r",stdin);
	//freopen("num10.out","w",stdout);
	memset(exboy,0,sizeof(exboy));
	memset(exgirl,0,sizeof(exgirl));
	memset(boy,false,sizeof(boy));
	memset(girl,false,sizeof(girl));
	read(n);
	int k; 
	for(int i=1;i<=n;i++)
	{
		read(k);
		for(int j=1;j<=31;j++)
			if((1<<j-1)&k)
			{
				exboy=1<<j-1)&k;
				add(i,j);
			}
	}
	for(int i=1;i<=n;i++)
	{
		memset(usedgirl,false,sizeof(usedgirl));
		memset(usedboy,false,sizeof(usedboy));
		while(!found(i))
		{
			for(int i=1)
			memset(usedgirl,false,sizeof(usedgirl));
			memset(usedboy,false,sizeof(usedboy));
			girl[1]=0;
		}
	}
	int ans=0;
	for(int i=1;i<=31;i++)if(girl[i])ans+=1<<i-1;
	std::cout<<ans;
	return 0;
}*/




#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN];   // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN];      // 每个妹子的期望值
int ex_boy[MAXN];       // 每个男生的期望值
bool vis_girl[MAXN];    // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN];     // 记录每一轮匹配匹配过的男生
int match[MAXN];        // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN];        // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
    vis_girl[girl]=true;
    for(int boy=0;boy<N;++boy)
	{
        if(vis_boy[boy])continue;//每一轮匹配 每个男生只尝试一次
        int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];
        if(gap==0)
		{  // 如果符合要求
            vis_boy[boy]=true;
            if(match[boy]==-1||dfs(match[boy]))
			{//找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
                match[boy]=girl;
                return true;
            }
        }
		else
		{
            slack[boy]=min(slack[boy],gap);//slack可以理解为该男生要得到女生的倾心
			//还需多少期望值 取最小值 备胎的样子
        }
    }
    return false;
}
int KM()
{
    memset(match, -1,sizeof match);    // 初始每个男生都没有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每个男生的期望值为0
    //每个女生的初始期望值是与她相连的男生最大的好感度
    for(int i=0;i<N;++i)
	{
        ex_girl[i]=love[i][0];
        for(int j=1;j<N;++j)
            ex_girl[i]=max(ex_girl[i],love[i][j]);
    }
    // 尝试为每一个女生解决归宿问题
    for (int i=0;i<N;++i)
	{
        fill(slack,slack+N,INF);    // 因为要取最小值 初始化为无穷大
        while(1)
		{
            // 为每个女生解决归宿问题的方法是 :如果找不到就降低期望值,直到找到为止 
            // 记录每轮匹配中男生女生是否被尝试匹配过
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);
            if (dfs(i)) break;  // 找到归宿 退出
            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d=INF;
            for(int j=0;j<N;++j)
                if(!vis_boy[j])d=min(d,slack[j]);
            for(int j=0;j<N;++j)
			{
                // 所有访问过的女生降低期望值
                if (vis_girl[j])ex_girl[j]-=d;
                // 所有访问过的男生增加期望值
                if (vis_boy[j])ex_boy[j]+=d;
                // 没有访问过的boy 因为girl们的期望值降低,距离得到女生倾心又进了一步!
                else slack[j]-=d;
            }
        }
    }
    // 匹配完成 求出所有配对的好感度的和
    int res=0;
    for(int i=0;i<N;++i)res+=love[match[i]][i];
    return res;
}
int main()
{
	//freopen("num1.in","r",stdin);
	//freopen("num1.out","w",stdout);
	memset(love,0,sizeof(love));
    std::cin>>N;
    for(int i=0;i<N;++i)
    {
    	int k;
    	scanf("%d",&k);
    	for(int j=1;j<=31;j++)
    		if((1<<j-1)&k)love[i][j]=1<<j-1;
	}
	printf("%d\n", KM());
    return 0;
}

信息

递交者
类型
递交
题目
奇数异或(国家集训队)
题目数据
下载
语言
C++
递交时间
2017-10-05 22:50:53
评测时间
2017-10-06 17:03:35
评测机
分数
40
总耗时
660ms
峰值内存
4.25 MiB