BZOJ 2744 [HEOI2012] 朋友圈

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2744

题意：

对于 A，B 两个点集，每个点均有一个权值。对于点集 A 中的两个互异元素，记它们的权值为 (i,j)，当且仅当 (i^j)%2=1 时它们间有边相连。
对于点集 B 中的两个互异元素，记它们的权值为 (i,j)，若 (i^j)%2=0 或 (i|j) 在二进制下有奇数个 1 时它们间有边相连，此处^记为异或，|记为或，给出 A，B 集间的连接关系，求整个图的最大团...

很神的一道好题....

首先如果是一般图的最大团问题.... 这个数据范围肯定是不可做的啦.... 所以我们考虑下这个图有什么特殊的性质.... 让我们先用人话重述一遍题意...

对于 A 集，仅在奇数和偶数间有边相连，对于 B 集，奇数和奇数间，偶数和偶数间，还有一个特殊情况间有边相连...

很明显，A 集是个二分图，它的性质比较优越... 考虑一下可知，A 集的最大团仅能为 0,1,2... 最大为 2.... 因为如果在一奇一偶以外再引入一个点必然与其中一个点没有边相连....

B 集的最大团不是很好搞... 我们取它的补图，即当且仅当奇偶不同且满足 (i|j) 在二进制下有偶数个 1 时有边相连，这样 B 图就也是个二分图啦

对于二分图，有一个性质， 它的最大点独立集就是它补图的最大团 ... 那么求最大点独立集即可， 二分图最大点独立集=sum-二分图最大匹配

因为 A 集只可能为答案做出 0,1,2 个点的贡献，我们分别讨论，枚举即可，每次我们只跑和在 A 集中选取的点有边相连的点...

然后如果我们各种 memset，暴力重构图的话是会 TLE 的... 所以我们要优化一下...

在下面给出的程序中，我们以 tag[] 数组记录当前点集 B 中的某点是否可以跑，vis[] 数组记录某次跑最大匹配时是否访问过某点，tim[] 数组记录在当前的匹配下 lk 数组是否被更新过

时间戳优化即可....T1 记录匹配次数，T2 记录 find 次数

有一个需要吐槽的地方... 不小心把"tim[to]!=T1"这里的 T1 全部处理成 T2，居然比正解跑的快 5 倍以上而且能过，事实上这里如果是 T2 是始终为真的... 那么... 貌似数据有点水？对于每个匹配只连第一个即可？这样貌似可以 O(1) 刷 rank 了吗... 算了，懒得刷了 qwq

(大概是正确的) 代码如下：

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 9000100
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
int A,B,m,T1,T2,ans;    
int a[210],b[3010];
int map[210][3010];
int tag[3010],vis[3010],tim[3010];
int lk[3010];
struct zgz
{
    int next,to;
}edge[M];
int cnt=1,head[M];
void add(int from,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
int count(int x)
{
    int ret=0;
    while(x)
    {
        ret+=x&1;
        x>>=1;
    }
    return ret;
}
bool find(int x)
{
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(tag[to]==T1&&vis[to]!=T2)
        {
            vis[to]=T2;
            if(tim[to]!=T1||!lk[to]||find(lk[to]))
            {
                tim[to]=T1;
                lk[to]=x;
                return 1;
            }
        }
    }
    return 0;
}
int solve()
{
    int tot=0;
    for(int i=1;i<=B;i++)
    if(tag[i]==T1)
    {
        T2++;
        if(find(i))tot++;
    }
    else tot++;
    return B-tot;
}
int main()
{
    A=read(),B=read(),m=read();
    for(int i=1;i<=A;i++)a[i]=read();
    for(int i=1;i<=B;i++)b[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        map[x][y]=1;
    }
    for(int i=1;i<=B;i++)
    if(b[i]&1)
    for(int j=1;j<=B;j++)
    if(!(b[j]&1))
    if(!(count(b[i]|b[j])&1))add(i,j);
    ans=max(ans,solve());
    for(int i=1;i<=A;i++)
    {
        T1++;
        for(int j=1;j<=B;j++)
        if(map[i][j])tag[j]=T1;
        ans=max(ans,solve()+1);
    }
    for(int i=1;i<=A;i++)
    if(a[i]&1)
    for(int j=i+1;j<=A;j++)
    if(!(a[j]&1))
    {
        T1++;
        for(int k=1;k<=B;k++)
        if(map[i][k]&&map[j][k])tag[k]=T1;
        ans=max(ans,solve()+2);
    }
    printf("%d",ans);
}

100

101

102

103

104

105

106

107

108

109

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 9000100

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int A,B,m,T1,T2,ans;

int a[210],b[3010];

int map[210][3010];

int tag[3010],vis[3010],tim[3010];

int lk[3010];

struct zgz

{

int next,to;

}edge[M];

int cnt=1,head[M];

void add(int from,int to)

{

edge[cnt].to=to;

edge[cnt].next=head[from];

head[from]=cnt++;

}

int count(int x)

{

int ret=0;

while(x)

{

ret+=x&1;

x>>=1;

}

return ret;

}

bool find(int x)

{

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

if(tag[to]==T1&&vis[to]!=T2)

{

vis[to]=T2;

if(tim[to]!=T1||!lk[to]||find(lk[to]))

{

tim[to]=T1;

lk[to]=x;

return 1;

}

return 0;

}

int solve()

{

int tot=0;

for(int i=1;i<=B;i++)

if(tag[i]==T1)

{

T2++;

if(find(i))tot++;

}

else tot++;

return B-tot;

}

int main()

{

A=read(),B=read(),m=read();

for(int i=1;i<=A;i++)a[i]=read();

for(int i=1;i<=B;i++)b[i]=read();

for(int i=1;i<=m;i++)

{

int x=read(),y=read();

map[x][y]=1;

}

for(int i=1;i<=B;i++)

if(b[i]&1)

for(int j=1;j<=B;j++)

if(!(b[j]&1))

if(!(count(b[i]|b[j])&1))add(i,j);

ans=max(ans,solve());

for(int i=1;i<=A;i++)

{

T1++;

for(int j=1;j<=B;j++)

if(map[i][j])tag[j]=T1;

ans=max(ans,solve()+1);

}

for(int i=1;i<=A;i++)

if(a[i]&1)

for(int j=i+1;j<=A;j++)

if(!(a[j]&1))

{

T1++;

for(int k=1;k<=B;k++)

if(map[i][k]&&map[j][k])tag[k]=T1;

ans=max(ans,solve()+2);

}

printf("%d",ans);

}

zgz233

BZOJ 2744 [HEOI2012] 朋友圈

BZOJ 3891 [Usaco2014 Dec]Piggy Back

BZOJ 网络流题目总结

l1ll5

Comments | NOTHING

zgz233