BZOJ 3532 Lis

发表于 | 更新于

Link

Solution

最小割+最小割可行边判断+退流

Tips

被坑。 论Dinic与ISAP的效率。 学网络流算法的时候听说ISAP更高效，就直接没看Dinic。做的几道网络流题也全都没有因为算法被卡过。 但是，今天被卡飞了。 ISAP写完，TLE。本地测试，最大的一个点需要4s。卡常数，最大的一个点还是3s。于是各种办法都没用。 发现网上过掉的程序几乎都是Dinic。学了Dinic。写出来调对之后很快就通过了。 以下纯属一个蒟蒻的自言自语 d[S]<N || num[x]==0。这是ISAP的终止条件。当对网络流进行局部调整的时候，如果两个点之间不联通，可能尝试绕出很多条增广路，才会判定出它们不联通。 加上计数器，计算一次ISAP不联通时的迭代次数，发现单次ISAP，1400个点的图最多居然出现了15W次无效的循环才结束。 而Dinic就每次O(n)O(n)一遍BFS就保证了在不联通时就能及时结束。 So，整体一遍的用ISAP，对图进行局部调整的用Dinic。 欢迎拍砖 欢迎吐槽

Code

ISAP

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
134
135
136
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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;}
const int MAXN=(700+10)<<1,MAXM=MAXN*MAXN,INF=0x1f1f1f1f;
using std::sort;
struct Edge{int to,cap,v,pre;}e[MAXM<<1];int id[MAXN],S,T,N,ec;
int 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;
	return ec-1;
}
int pree[MAXN],d[MAXN],num[MAXN],now[MAXN];
int Aug(int T)
{
	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;
}
bool BFS(int S,int T)
{
	static int Q[MAXN],he,ta;
	memset(d,-1,sizeof(d));d[T]=0;
	Q[he=ta=1]=T;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(e[i^1].cap>e[i^1].v && d[u]==-1)
			{
				d[u]=d[cur]+1;
				Q[++ta]=u;
			}
		}
	}
	return d[S]!=-1;
}
int ISAP(int S=S,int T=T)
{
	if(!BFS(S,T)) return 0;
	memset(num,0,sizeof(num));
	memset(pree,0,sizeof(pree));
	memcpy(now,id,sizeof(id));
	for(int i=0;i<=N;i++) num[d[i]]++;
	int flow=0,cur=S;
	while(d[S]<N)
	{
		if(cur==T)
		{
			flow+=Aug(T);
			cur=S;
		}
		bool adv=0;
		for(int i=now[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(e[i].cap>e[i].v && d[u]+1==d[cur])
			{
				adv=1;
				now[cur]=i;
				pree[cur=u]=i;
				break;
			}
		}
		if(!adv)
		{
			if(--num[d[cur]]==0) break;
			int mind=N-1;
			for(int i=(now[cur]=id[cur]);i;i=e[i].pre)
				if(e[i].cap>e[i].v) chkmn(mind,d[e[i].to]);
			++num[d[cur]=mind+1];
			if(cur!=S) cur=e[pree[cur]^1].to;
		}
	}
	return flow;
}
void CLEAR(){ec=1;memset(id,0,sizeof(id));}
int c[MAXN];
bool cmp(int i,int j){return c[i]<c[j];}
void WORK()
{
	static int a[MAXN],b[MAXN],f[MAXN],d[MAXN],s[MAXN],slen,link[MAXN];
	#define node(x,y) (x+y*n)
	int n;get(n);S=0,T=node(n,1)+1,N=T+1;
	for(int i=1;i<=n;i++) get(a[i]);
	for(int i=1;i<=n;i++) get(b[i]);
	for(int i=1;i<=n;i++) get(c[i]),d[i]=i;
	sort(d+1,d+1+n,cmp);
	int maxlen=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
			if(a[j]<a[i]) chkmx(f[i],f[j]+1);
		chkmx(maxlen,f[i]);
	}
	for(int i=1;i<=n;i++)
		if(f[i]==1) Adde(S,node(i,0),INF);
		else if(f[i]==maxlen) Adde(node(i,1),T,INF);
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[j]<a[i] && f[j]+1==f[i])
				Adde(node(j,1),node(i,0),INF);
	for(int i=1;i<=n;i++) link[i]=Adde(node(i,0),node(i,1),b[i]);
	printf("%d ",ISAP());slen=0;
	for(int i=1,j;i<=n;i++)
	{
		if(BFS(node(d[i],0),node(d[i],1))) continue;
		s[++slen]=d[i];
		ISAP(node(d[i],0),S);
		ISAP(T,node(d[i],1));
		j=link[d[i]];
		e[j].cap=e[j].v=e[j^1].cap=e[j^1].v=0;
	}
	printf("%d\n",slen);
	sort(s+1,s+1+slen);
	for(int i=1;i<=slen;i++)
		printf("%d%s",s[i],i==slen?"\n":" ");
}
int main()
{
	int T;get(T);
	while(T--) CLEAR(),WORK();
	return 0;
}

Dinic

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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;}
const int MAXN=(700+10)<<1,MAXM=MAXN*MAXN,INF=0x1f1f1f1f;
using std::sort;
using std::min;

struct Edge{int to,cap,v,pre;}e[MAXM<<1];int id[MAXN],S,T,N,ec;
int 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;
	return ec-1;
}
int pree[MAXN],d[MAXN],now[MAXN];
bool BFS(int S,int T)
{
	static int Q[MAXN],he,ta;
	memset(d,0,sizeof(d));
	Q[he=ta=1]=S;d[S]=1;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(e[i].cap>e[i].v && !d[u])
			{
				d[u]=d[cur]+1;Q[++ta]=u;
				if(u==T) return 1;
			}
		}
	}
	return 0;
}
int DFS(int pos,int t,int cmf)
{
	if(pos==t || cmf==0) return cmf;
	int flow=0,minf;
	for(int &i=now[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(d[u]==d[pos]+1 && (minf=DFS(u,t,min(cmf,e[i].cap-e[i].v))))
		{
			e[i].v+=minf;e[i^1].v-=minf;
			flow+=minf;cmf-=minf;
			if(!cmf) break;
		}
	}
	return flow;
}
int Dinic(int S,int T)
{
	int flow=0;
	while(BFS(S,T))
	{
		memcpy(now,id,sizeof(id));
		flow+=DFS(S,T,INF);
	}
	return flow;
}
void CLEAR(){ec=1;memset(id,0,sizeof(id));}
int c[MAXN];
bool cmp(int i,int j){return c[i]<c[j];}
void WORK()
{
	static int a[MAXN],b[MAXN],f[MAXN],d[MAXN],s[MAXN],slen,link[MAXN];
	#define node(x,y) (x+y*n)
	int n;get(n);S=0,T=node(n,1)+1,N=T+1;
	for(int i=1;i<=n;i++) get(a[i]);
	for(int i=1;i<=n;i++) get(b[i]);
	for(int i=1;i<=n;i++) get(c[i]),d[i]=i;
	sort(d+1,d+1+n,cmp);
	int maxlen=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
			if(a[j]<a[i]) chkmx(f[i],f[j]+1);
		chkmx(maxlen,f[i]);
	}
	for(int i=1;i<=n;i++)
		if(f[i]==1) Adde(S,node(i,0),INF);
		else if(f[i]==maxlen) Adde(node(i,1),T,INF);
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[j]<a[i] && f[j]+1==f[i])
				Adde(node(j,1),node(i,0),INF);
	for(int i=1;i<=n;i++) link[i]=Adde(node(i,0),node(i,1),b[i]);
	printf("%d ",Dinic(S,T));slen=0;
	for(int i=1,j;i<=n;i++)
	{
		if(BFS(node(d[i],0),node(d[i],1))) continue;
		s[++slen]=d[i];
		Dinic(node(d[i],0),S);
		Dinic(T,node(d[i],1));
		j=link[d[i]];
		e[j].cap=e[j].v=e[j^1].cap=e[j^1].v=0;
	}
	printf("%d\n",slen);
	sort(s+1,s+1+slen);
	for(int i=1;i<=slen;i++)
		printf("%d%s",s[i],i==slen?"\n":" ");
}
int main()
{
//	freopen("input","r",stdin);
	int T;get(T);
	while(T--) CLEAR(),WORK();
	return 0;
}