BZOJ1324

@OceanEye7年前

05/2

20:04

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

有些炸裂的题解

题目是一道最大点独立集，比较裸的那种

最大点独立集=最小点覆盖集的补集

然后套最小点覆盖集用sum-tot_flow即可

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	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 E 100010
#define N 10050

struct Tedge
{
	int from,to,cap,flow;
}edge[E];
#define TO edge[i].to
#define FROM edge[i].from
#define FLO (edge[i].cap-edge[i].flow)
int e_tot,fst[N],NXT[E];
#define calc(x,y) ((x-1)*m+y)
#define S 0
#define T N-1

void add_e(int _,int __,int ___)
{
	edge[e_tot].to=__; edge[e_tot].from=_; edge[e_tot].cap=___; edge[e_tot].flow=0;
	NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	edge[e_tot].to=_; edge[e_tot].from=__; edge[e_tot].cap=___; edge[e_tot].flow=___;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int dist[N],cnt[N],cur[N],p[N];

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

int Augment()
{
	static int ret,node,i;
	ret=INF; node=T;
	while(node!=S)
	{
		i=p[node];
		ret=min(ret,FLO);
		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;
	bool flag;
	for(int i=0;i<N;i++) cur[i]=fst[i];
	while(dist[S]<N)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(int i=cur[node];~i;i=NXT[i])
		{
			if(dist[TO]!=dist[node]-1||!FLO) continue;
			flag=true;
			p[TO]=i;
			cur[node]=i;
			node=TO;
			break;
		}
		if(flag) continue;
		int M=N+5;
		cur[node]=fst[node];
		for(int i=fst[node];~i;i=NXT[i])
		{
			if(!FLO) continue;
			M=min(dist[TO]+1,M);
		}
		if(!--cnt[dist[node]]) return ret;
		dist[node]=M;
		cnt[M]++;
		if(node!=S) node=edge[p[node]].from;
	}
	return ret;
}

int a[105][105],tot,n,m;

const int _x[4]={0,0,1,-1},_y[4]={1,-1,0,0};

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(a[i][j]),tot+=a[i][j];
	int _,__;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			if((i^j)&1)
			{
				add_e(calc(i,j),T,a[i][j]);
				continue;
			}
			add_e(S,calc(i,j),a[i][j]);
			for(int k=0;k<4;k++)
			{
				_=i+_x[k]; __=j+_y[k];
				if(_<=0||_>n||__<=0||__>m) continue;
				add_e(calc(i,j),calc(_,__),INF);
			}
		}
}

int main()
{
	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

158

159

160

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <queue>

#define ll long long

#define INF 1000000000

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

char cc; int C;

template <class T>

void read( T &x )

{

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

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 E 100010

#define N 10050

struct Tedge

{

int from,to,cap,flow;

}edge[E];

#define TO edge[i].to

#define FROM edge[i].from

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

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

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

#define S 0

#define T N-1

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

{

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

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

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

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

}

int dist[N],cnt[N],cur[N],p[N];

bool bfs()

{

int x;

queue <int> Q;

dist[T]=1;

cnt[1]=1;

Q.push(T);

while(!Q.empty())

{

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

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

{

if(dist[TO]||FLO) continue;

cnt[dist[TO]=dist[x]+1]++;

Q.push(TO);

}

return dist[S]!=0;

}

int Augment()

{

static int ret,node,i;

ret=INF; node=T;

while(node!=S)

{

i=p[node];

ret=min(ret,FLO);

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;

bool flag;

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

while(dist[S]<N)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

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

{

if(dist[TO]!=dist[node]-1||!FLO) continue;

flag=true;

p[TO]=i;

cur[node]=i;

node=TO;

break;

}

if(flag) continue;

int M=N+5;

cur[node]=fst[node];

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

{

if(!FLO) continue;

M=min(dist[TO]+1,M);

}

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

dist[node]=M;

cnt[M]++;

if(node!=S) node=edge[p[node]].from;

}

return ret;

}

int a[105][105],tot,n,m;

const int _x[4]={0,0,1,-1},_y[4]={1,-1,0,0};

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(a[i][j]),tot+=a[i][j];

int _,__;

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

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

{

if((i^j)&1)

{

add_e(calc(i,j),T,a[i][j]);

continue;

}

add_e(S,calc(i,j),a[i][j]);

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

{

_=i+_x[k]; __=j+_y[k];

if(_<=0||_>n||__<=0||__>m) continue;

add_e(calc(i,j),calc(_,__),INF);

}

int main()

{

pre();

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

return 0;

}

OceanEye's Blog

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

@OceanEye7年前

BZOJ1324

BZOJ1324

撤销评论

近期文章

标签