BZOJ4808

@OceanEye7年前

05/9

21:15

OceanEye 撰写 BZOJ 最小割网络流无回复

题目名字很有趣

但是看完题面会发现这就是个黑白染色最小割

网络流大法好，ISAP直接跑

好像这几道题是一个系列的233

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#define ll long long 
#define INF 1000000000
char cc; int C;
#define p(x) ('0'<=x&&x<='9')
template <class T>
void read( T &x )
{
	cc=getchar(); C=1; x=0;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}
using namespace std;

#define N 205
#define E 800000
#define S 0
#define T 40009

struct Tedge
{
	int from,to,cap,flow;
}edge[E];
int e_tot,NXT[E],fst[40010];
#define TO edge[i].to
#define FROM edge[i].from
#define FL (edge[i].cap-edge[i].flow)
void add_e(int _,int __,int cap)
{
	edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=cap; edge[e_tot].flow=0;
	NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=cap; edge[e_tot].flow=cap;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int d[40010],p[40010],cur[40010],cnt[40010];
int mp[N][N],n,m,tot;

bool bfs()
{
	int x,i;
	d[T]=1;
	queue <int> Q;
	Q.push(T);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		cnt[d[x]]++;
		for(i=fst[x];~i;i=NXT[i])
		{
			if(d[TO]||FL) continue;
			d[TO]=d[x]+1;
			Q.push(TO);
		}
	}
	return d[S]!=0;
}

int Augment()
{
	int node,ret,i;
	node=T; ret=INF;
	while(node!=S)
	{
		i=p[node];
		ret=min(ret,FL);
		node=FROM;
	}
	node=T;
	while(node!=S)
	{
		i=p[node];
		edge[i].flow+=ret;
		edge[i^1].flow-=ret;
		node=FROM;
	}
	return ret;
}

int ISAP()
{
	if(!bfs()) return 0;
	int node=S,ret=0,M,i;
	bool flag;
	for(int i=0;i<40010;i++) cur[i]=fst[i];
	while(d[S]<=tot+2)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(i=cur[node];~i;i=NXT[i])
			if(d[TO]==d[node]-1&&FL)
			{
				flag=true;
				p[TO]=cur[node]=i;
				node=TO;
				break;
			}
		if(flag) continue;
		M=tot+5;
		for(cur[node]=i=fst[node];~i;i=NXT[i])
			if(FL) M=min(M,d[TO]+1);
		if(!--cnt[d[node]]) return ret;
		cnt[d[node]=M]++;
		node!=S?node=edge[p[node]].from:node=S;
	}
	return ret;
}

const int _x[8]={1,1,2,2,-1,-1,-2,-2},_y[8]={2,-2,1,-1,2,-2,1,-1};

#define calc(x,y) ( (x-1)*m+y )

void pre()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) read(mp[i][j]);
	int x,y,pt;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]) continue;
			tot++;
			pt=calc(i,j);
			if((i^j)&1)
			{
				add_e(S,pt,1);
				for(int k=0;k<8;k++)
				{
					x=_x[k]+i; y=_y[k]+j;
					if(mp[x][y])continue;
					if(x>n||x<=0||y>m||y<=0) continue;
					add_e(pt,calc(x,y),INF);
				}
			}
			else
				add_e(pt,T,1);
		}
}

int main()
{
//	freopen("BZOJ4808.in","r",stdin);
	pre();
	printf("%d",tot-ISAP());
	return 0;
}

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

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <queue>

#define ll long long

#define INF 1000000000

char cc; int C;

#define p(x) ('0'<=x&&x<='9')

template <class T>

void read( T &x )

{

cc=getchar(); C=1; x=0;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 205

#define E 800000

#define S 0

#define T 40009

struct Tedge

{

int from,to,cap,flow;

}edge[E];

int e_tot,NXT[E],fst[40010];

#define TO edge[i].to

#define FROM edge[i].from

#define FL (edge[i].cap-edge[i].flow)

void add_e(int _,int __,int cap)

{

edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=cap; edge[e_tot].flow=0;

NXT[e_tot]=fst[_]; fst[_]=e_tot++;

edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=cap; edge[e_tot].flow=cap;

NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int d[40010],p[40010],cur[40010],cnt[40010];

int mp[N][N],n,m,tot;

bool bfs()

{

int x,i;

d[T]=1;

queue <int> Q;

Q.push(T);

while(!Q.empty())

{

x=Q.front(); Q.pop();

cnt[d[x]]++;

for(i=fst[x];~i;i=NXT[i])

{

if(d[TO]||FL) continue;

d[TO]=d[x]+1;

Q.push(TO);

}

return d[S]!=0;

}

int Augment()

{

int node,ret,i;

node=T; ret=INF;

while(node!=S)

{

i=p[node];

ret=min(ret,FL);

node=FROM;

}

node=T;

while(node!=S)

{

i=p[node];

edge[i].flow+=ret;

edge[i^1].flow-=ret;

node=FROM;

}

return ret;

}

int ISAP()

{

if(!bfs()) return 0;

int node=S,ret=0,M,i;

bool flag;

for(int i=0;i<40010;i++) cur[i]=fst[i];

while(d[S]<=tot+2)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

for(i=cur[node];~i;i=NXT[i])

if(d[TO]==d[node]-1&&FL)

{

flag=true;

p[TO]=cur[node]=i;

node=TO;

break;

}

if(flag) continue;

M=tot+5;

for(cur[node]=i=fst[node];~i;i=NXT[i])

if(FL) M=min(M,d[TO]+1);

if(!--cnt[d[node]]) return ret;

cnt[d[node]=M]++;

node!=S?node=edge[p[node]].from:node=S;

}

return ret;

}

const int _x[8]={1,1,2,2,-1,-1,-2,-2},_y[8]={2,-2,1,-1,2,-2,1,-1};

#define calc(x,y) ( (x-1)*m+y )

void pre()

{

memset(fst,-1,sizeof(fst));

read(n); read(m);

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

for(int j=1;j<=m;j++) read(mp[i][j]);

int x,y,pt;

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

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

{

if(mp[i][j]) continue;

tot++;

pt=calc(i,j);

if((i^j)&1)

{

add_e(S,pt,1);

for(int k=0;k<8;k++)

{

x=_x[k]+i; y=_y[k]+j;

if(mp[x][y])continue;

if(x>n||x<=0||y>m||y<=0) continue;

add_e(pt,calc(x,y),INF);

}

else

add_e(pt,T,1);

}

int main()

{

// freopen("BZOJ4808.in","r",stdin);

pre();

printf("%d",tot-ISAP());

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ4808

BZOJ4808

撤销评论

近期文章

标签