BZOJ 2744 朋友圈

发表于 | 更新于

Link

Solution

无数教训

##技巧

###补图（反图） 最大团为NP完全问题，而该图的最大团较为特殊——是二分图上的最大团。可以知道，最大团为点集的数目-最大匹配数。这样，求解最大团问题可以建立原图的补图，即一切有的边删去，一切没有的边加上。在该图上做二分图匹配，用总数-匹配数即为最大独立集，也就是原图的最大团。

###时间戳 为了避免每次都用memset()memset()清空数组，可以定义时间戳int ud代替bool ud数组。每次执行都将timeline++，将判断条件!ud[i]改为ud[i]!=timeline。为了保险，时间戳的增加一定要在每次执行之前进行，否则可能因为第一次执行没有增加而错位，导致这道题目WA了一下午。

##匈牙利的实现！

#Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 3010
#define MAXM 9000000
using namespace std;
int A,B;
int an[MAXN],bn[MAXN],match[MAXN];
int ud[MAXN],time=0;
int fob[MAXN],cnt=0;
int map[MAXN][MAXN];
 
int ec=0,pre[MAXM],e[MAXM],id[MAXN];
 
bool OK(int x,int y)
{
    int temp=x|y;
    int res=0;
    while(temp)
    {
        temp-=(temp&(-temp));
        res++;
    }
    return ~res&1;
}
void addedge(int u,int v)
{
    ec++;
    pre[ec]=id[u];
    e[ec]=v;
    id[u]=ec;
}
bool Hgr(int x)
{
    if(fob[x]==cnt) return false;
    for(int i=id[x];i;i=pre[i])
    {
        if((fob[e[i]]!=cnt)&&(ud[e[i]]!=time))
        {
            ud[e[i]]=time;
            //we must give it a mark
            //cause when go deep down ,may find itself again , then RE
            if(match[e[i]]==0||Hgr(match[e[i]]))
            {
                match[e[i]]=x;
                return true;
            }
        }
    }
	//ud[x]=time;
	return false;
}
int Max()
{
    int re=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=B;i++)
    {
    	if(bn[i]&1)
 		{
			time++;
        	if(Hgr(i))
            	re++;
		}
    }
    return B-re;
}
int Max(int x)
{
    cnt++;
    int temp=0;
    for(int i=1;i<=B;i++)
        if(!map[x][i]) fob[i]=cnt,temp++;
    return Max()-temp;   
}
int Max(int x,int y)
{
    cnt++;
    int temp=0;
    for(int i=1;i<=B;i++)
        if(!map[x][i] || !map[y][i]) fob[i]=cnt,temp++;
    return Max()-temp;
}
int main()
{
  	freopen("input.txt","r",stdin);
  	freopen("output.txt","w",stdout);
    int m;
    scanf("%d%d%d",&A,&B,&m);
    for(int i=1;i<=A;i++)
        scanf("%d",&an[i]);
    for(int i=1;i<=B;i++)
        scanf("%d",&bn[i]);
    int t1,t2;
    memset(map,0,sizeof(map));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&t1,&t2);
        map[t1][t2]=true;
    }   
    memset(ud,0,sizeof(ud));
    memset(fob,-1,sizeof(fob));
    for(int i=1;i<=B;i++)
    {
        if(bn[i]&1)
            for(int j=1;j<=B;j++)
                if(~bn[j]&1)
                    if(OK(bn[i],bn[j])) 
                        addedge(i,j);
    }
    int ans=Max();
    for(int i=1;i<=A;i++)
    {
        ans=max(ans,Max(i)+1);
    }
    for(int i=1;i<=A;i++)
    {
        if(an[i]%2==1)
            for(int j=1;j<=A;j++)
                if(an[j]%2==0)
                    ans=max(ans,Max(i,j)+2);
    }
    printf("%d",ans);
    return 0;
}

再做

二分图没有奇环。 匹配前应该要染色吧。

But Why 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define llred(x) scanf("%lld",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return b<a?a=b,1:0;}
typedef long long LL;
const int MAXA=200+1,MAXB=3000+1,MAXN=MAXA+MAXB,MAXM=MAXN*MAXN;
struct Edge
{
	int to;
}e[MAXM];int pre[MAXM],id[MAXN],ec;
void Adde(int f,int t)
{
	e[++ec].to=t;pre[ec]=id[f];id[f]=ec;
	e[++ec].to=f;pre[ec]=id[t];id[t]=ec;
}
bool re[MAXA][MAXB];int a[MAXA],b[MAXB];
int us[MAXN],U,A,B;
inline bool ud(int x) {return us[x]==U;}
inline void used(int x){ us[x]=U;}
int uab[MAXA],T;
inline bool fob(int x){return x<=A && uab[x]!=T;}
int count(int x)
{
	int res=0;
	while(x)
	{
		x-=x & -x;
		res++;
	}
	return res;
}
int color[MAXN];
void Bip(int pos)
{
	for(int i=id[pos],u=e[i].to;i;i=pre[i],u=e[i].to)
	{
		if(!color[u] && !fob(u))
		{
			color[u]=color[pos]^1;
			Bip(u);
		}
	}
}
int match[MAXN];
bool Aug(int pos)//左找右 
{
	if(!pos) return 1;
	for(int i=id[pos],u=e[i].to;i;i=pre[i],u=e[i].to)
	{
		if(ud(u) || fob(u)) continue;
		used(u);
		if(Aug(match[u]))
		{
			match[u]=pos;
			return 1;
		}
	}
	return 0;
}
int Lp[MAXN],lc;
int Match()
{
	for(int i=1;i<=A+B;i++)
		color[i]=match[i]=0;
	for(int i=1;i<=A+B;i++)
		if(!fob(i) && !color[i])
			color[i]=2,Bip(i);
	lc=0;
	for(int i=1;i<=A+B;i++)
		if(color[i]==2)
			Lp[++lc]=i;
	int ANS=0;
	for(int i=1;i<=lc;i++)
	{
		++U;
		if(Aug(Lp[i]))
			ANS++;
	}
	return ANS;
}
void CLEAR()
{
	memset(id,0,sizeof(id));ec=0;
	memset(re,0,sizeof(re));
}
void WORK()
{
	CLEAR();
	int t1,t2,t3,m;
	red(A),red(B),red(m);
	for(int i=1;i<=A;i++)
		red(a[i]);
	for(int i=1;i<=B;i++)
		red(b[i]); 
	for(int i=1;i<=m;i++)
	{
		red(t1),red(t2);
		re[t1][t2]=1;
	}
	int ANS=0;
	for(int i=1;i<A;i++)
		for(int j=i+1;j<=A;j++)
			if((a[i]&1)==(a[j]&1))
				Adde(i,j);
	for(int i=1;i<=A;i++)
		for(int j=1;j<=B;j++)
			if(!re[i][j])
				Adde(i,j+A);
	for(int i=1;i<B;i++)
		for(int j=i+1;j<=B;j++)
			if(!((((b[i]^b[j])&1)==0) || (count(b[i] | b[j])&1)))
				Adde(i+A,j+A);
	++T;chkmx(ANS,B-Match());
	for(int i=1;i<=A;i++)
		uab[i]=++T,chkmx(ANS,B+1-Match());
	for(int i=1;i<A;i++)
		for(int j=i+1;j<=A;j++)
			if((a[i]&1)!=(a[j]&1))
			{
				uab[i]=uab[j]=++T;
				chkmx(ANS,B+2-Match());
			}
	printf("%d\n",ANS);
}
int main()
{
	freopen("input","r",stdin);
	//int T;red(T);
	//while(T--)
		WORK();
	return 0;
}