发表于 | 更新于

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;
}

发表于 | 更新于

Link

Solution

最小割的可行边和必须边

最小割

求出最大流后，从源点开始沿残量网络BFS，标记能够到达的点。 连接已标记的点和未标记的点的正向边就是该网络的一个最小割集。

必须边

性质

  1. 满流
  2. 残余网络中SS能到fromfrom、toto能到TT。

求法

SCC之后，看是否 。

可行边

性质

  1. 满流
  2. 删掉之后在残余网络中找不到u到v的路径。

求法

SCC之后，看是否 。

好吧这个还是记结论吧。。

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
126
127
128
129
130
131
132
133
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define getc() getchar()
#define putc(x) putchar(x)
#define puts(x) printf("%s",x)
#define foreach(it,x) for(typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())

typedef long long ll;

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 a>b?a=b,1:0;}

using std::max;
using std::min;

const int INF=0X1F1F1F1F,MAXN=4000+11,MAXM=60000+11;
namespace ISAP
{
	struct Edge{int to,cap,v,pre;}e[MAXM<<1];int id[MAXN],ec=1,s,t,n;
	void Adde(int f,int t,int cap)
	{
		e[++ec].to=t;e[ec].cap=cap;e[ec].v=0;e[ec].pre=id[f];id[f]=ec;
		e[++ec].to=f;e[ec].cap=0;e[ec].v=0;e[ec].pre=id[t];id[t]=ec;
	}
	int d[MAXN],num[MAXN],pree[MAXN],arc[MAXN];
	int Aug()
	{
		int minf=INF;
		for(int i=pree[t];i;i=pree[e[i^1].to])
			chkmn(minf,e[i].cap-e[i].v);
		for(int i=pree[t];i;i=pree[e[i^1].to])
			e[i].v+=minf,e[i^1].v-=minf;
		return minf;
	}
	int MaxFlow()
	{
		memcpy(arc,id,sizeof(id));
		num[0]=n;
		int flow=0,pres=s,adv;
		while(d[s]<n)
		{
			if(pres==t)
			{
				flow+=Aug();
				pres=s;
			}
			adv=0;
			for(int &i=arc[pres];i;i=e[i].pre)
			{
				int u=e[i].to;
				if(e[i].cap>e[i].v && d[pres]==d[u]+1)
				{
					adv=1;
					pree[pres=u]=i;
					break;
				}
			}
			if(!adv)
			{
				if(--num[d[pres]]==0) break;
				arc[pres]=id[pres];
				int mind=n-1;
				for(int i=id[pres];i;i=e[i].pre)
					if(e[i].cap>e[i].v) 
						chkmn(mind,d[e[i].to]);
				num[d[pres]=mind+1]++;
				if(pres!=s) pres=e[pree[pres]^1].to;
			}
		}
		return flow;
	}	
}using namespace ISAP;
int dc,dfn[MAXN],low[MAXN],stack[MAXN],top,sc,sn[MAXN];
bool instack[MAXN];
void DFS(int pos)
{
	instack[stack[++top]=pos]=1;
	dfn[pos]=low[pos]=++dc;
	for(int i=id[pos];i;i=e[i].pre)
	{
		if(e[i].cap==e[i].v) continue;
		int u=e[i].to;
		if(!dfn[u])
		{
			DFS(u);
			chkmn(low[pos],low[u]);
		}
		else if(instack[u])
			chkmn(low[pos],dfn[u]);
	}
	if(dfn[pos]==low[pos])
	{
		++sc;
		while(stack[top+1]!=pos)
		{
			sn[stack[top]]=sc;
			instack[stack[top--]]=0;
		}
	}
}
int main()
{
	freopen("input","r",stdin);
	int m;
	get(n),get(m),get(s),get(t);
	for(int i=1;i<=m;++i)
	{
		int u,v,c;get(u),get(v),get(c);
		Adde(u,v,c);
	}
	int flow=MaxFlow();
	for(int i=1;i<=n;++i)
		if(!dfn[i])
		{
			//dc=0;
			DFS(i);
		}
	for(int i=1;i<=m;++i)
	{
		if(e[i<<1].cap!=e[i<<1].v) 
		{
			puts("0 0\n");
			continue;
		}
		int to=e[i<<1].to,from=e[i<<1|1].to;//rev.
		put(sn[from]!=sn[to]),putc(' '),put(sn[s]==sn[from] && sn[t]==sn[to]),putc('\n');
	}
	return 0;
}