网络流 – OceanEye's Blog

Date Time

17/06/10 13:56

Author

OceanEye

Tags

BZOJ, 网络流

Leave a Reply

BZOJ3698

Description

XWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。
XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。
称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作（可以是上取整或者下取整），使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

Input

第一行一个整数N,N ≤ 100。
接下来N行每行包含N个绝对值小于等于1000的实数，最多一位小数。

Output

输出一行，即取整后A矩阵的元素之和的最大值。无解输出No。

Sample Input

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0

Sample Output

129

HINT

【数据规模与约定】

有10组数据，n的大小分别为10,20,30…100。

【样例说明】

样例中取整后满足XWW性的和最大的矩阵为：

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

朴素的建图，只是跑的网络流模式变了

然后就可以随便艹了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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 EE 80000
#define N 300
#define source 0
#define sink N-1
#define source_ N-2
#define sink_ N-3
struct Tedge
{
	int to,flow;
}edge[EE];
int e_tot,nxt[EE],fst[N];
#define E edge[i]
#define FLOW E.flow
#define TO E.to
#define NXT nxt[i]
#define calc(i) (n+i)
void add_e(int from,int to,int flow)
{
	static int &i=e_tot;
	TO=to; FLOW=flow; NXT=fst[from]; fst[from]=i++;
	TO=from; FLOW=0; NXT=fst[to]; fst[to]=i++;
}

double a[N][N];
int imp[N],in[N];
int n,S,T;
void init()
{
	int _;
	memset(fst,-1,sizeof(fst));
	read(n);
	For(i,1,n)
		for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]);
	For(i,1,n-1)
		for(int j=1;j<n;j++)
		{
			_=(int)floor(a[i][j]);
			if(ceil(a[i][j])!=_) add_e(i,calc(j),1);
			in[i]-=_; in[calc(j)]+=_;
		}
	For(i,1,n-1)
	{
		_=floor(a[i][n]);
		in[i]+=_;
		in[source]-=_;
		if(ceil(a[i][n])!=_) add_e(source,i,1);
	}
	For(i,1,n-1)
	{
		_=floor(a[n][i]);
		in[sink]+=_;
		in[calc(i)]-=_;
		if(ceil(a[n][i])!=_) add_e(calc(i),sink,1);
	}
	add_e(sink,source,INF);
	For(i,0,N-1) if(in[i]) 
	{
		in[i]>0?add_e(source_,i,in[i]):add_e(i,sink_,-in[i]);
		imp[i]=e_tot-2;
	}
}
int cnt[N],d[N];
bool bfs()
{
	memset(d,0,sizeof(d));
	memset(cnt,0,sizeof(cnt));
	static int queue[65540],x;
	static unsigned short int he=0,ta=0;
	queue[++he]=T;
	d[T]=1;
	while(he!=ta)
	{
		x=queue[++ta]; cnt[d[x]]++;
		for(int i=fst[x];~i;i=NXT) if(!d[TO]&&edge[i^1].flow)
		{ d[TO]=d[x]+1; queue[++he]=TO; }
	}
	return d[S];
}
void cp(int &x,int y) { x>y?x=y:x; }
int p[N];

int Augment()
{
	static int node,c,i;
	node=T; c=INF;
	while(node!=S)
	{
		i=p[node]; cp(c,FLOW);
		node=edge[i^1].to;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c;
		i^=1; FLOW+=c;
		node=TO;
	}
	return c;
}

int ISAP()
{
	static int node,cur[N],ret;
	static bool flag;
	if(!bfs()) return 0;
	node=S; ret=0;
	for(int i=0;i<N;i++) cur[i]=fst[i];
	while(d[S]<n*2+5)
	{
		if(node==T)
		{
			ret+=Augment();
			node=S;
		}
		flag=false;
		for(int i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)
		{
			p[TO]=i;
			cur[node]=i;
			node=TO;
			flag=true;
			break;
		}
		if(flag) continue;
		int M=N-1;
		if(!--cnt[d[node]]) break;
		for(int i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1);
		cnt[d[node]=M]++;
		cur[node]=fst[node];
		node==S?node:node=edge[p[node]^1].to;
	}
	return ret;
}

bool check()
{
	For(i,0,N-1) if(imp[i]) if(edge[imp[i]].flow) return false;
	return true;
}

int main()
{
	init();
	S=source_,T=sink_;
	ISAP();
//	printf("%d\n",ISAP());
	if(!check())
	{
		puts("-1");
		return 0;
	}
	S=source,T=sink;
	printf("%d\n",ISAP()*3);
	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

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#define ll long long

#define INF 1000000000

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

#define For(i,l,r) for(int i=l;i<=r;i++)

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 EE 80000

#define N 300

#define source 0

#define sink N-1

#define source_ N-2

#define sink_ N-3

struct Tedge

{

int to,flow;

}edge[EE];

int e_tot,nxt[EE],fst[N];

#define E edge[i]

#define FLOW E.flow

#define TO E.to

#define NXT nxt[i]

#define calc(i) (n+i)

void add_e(int from,int to,int flow)

{

static int &i=e_tot;

TO=to; FLOW=flow; NXT=fst[from]; fst[from]=i++;

TO=from; FLOW=0; NXT=fst[to]; fst[to]=i++;

}

double a[N][N];

int imp[N],in[N];

int n,S,T;

void init()

{

int _;

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

read(n);

For(i,1,n)

for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]);

For(i,1,n-1)

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

{

_=(int)floor(a[i][j]);

if(ceil(a[i][j])!=_) add_e(i,calc(j),1);

in[i]-=_; in[calc(j)]+=_;

}

For(i,1,n-1)

{

_=floor(a[i][n]);

in[i]+=_;

in[source]-=_;

if(ceil(a[i][n])!=_) add_e(source,i,1);

}

For(i,1,n-1)

{

_=floor(a[n][i]);

in[sink]+=_;

in[calc(i)]-=_;

if(ceil(a[n][i])!=_) add_e(calc(i),sink,1);

}

add_e(sink,source,INF);

For(i,0,N-1) if(in[i])

{

in[i]>0?add_e(source_,i,in[i]):add_e(i,sink_,-in[i]);

imp[i]=e_tot-2;

}

int cnt[N],d[N];

bool bfs()

{

memset(d,0,sizeof(d));

memset(cnt,0,sizeof(cnt));

static int queue[65540],x;

static unsigned short int he=0,ta=0;

queue[++he]=T;

d[T]=1;

while(he!=ta)

{

x=queue[++ta]; cnt[d[x]]++;

for(int i=fst[x];~i;i=NXT) if(!d[TO]&&edge[i^1].flow)

{ d[TO]=d[x]+1; queue[++he]=TO; }

}

return d[S];

}

void cp(int &x,int y) { x>y?x=y:x; }

int p[N];

int Augment()

{

static int node,c,i;

node=T; c=INF;

while(node!=S)

{

i=p[node]; cp(c,FLOW);

node=edge[i^1].to;

}

node=T;

while(node!=S)

{

i=p[node]; FLOW-=c;

i^=1; FLOW+=c;

node=TO;

}

return c;

}

int ISAP()

{

static int node,cur[N],ret;

static bool flag;

if(!bfs()) return 0;

node=S; ret=0;

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

while(d[S]<n*2+5)

{

if(node==T)

{

ret+=Augment();

node=S;

}

flag=false;

for(int i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)

{

p[TO]=i;

cur[node]=i;

node=TO;

flag=true;

break;

}

if(flag) continue;

int M=N-1;

if(!--cnt[d[node]]) break;

for(int i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1);

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

cur[node]=fst[node];

node==S?node:node=edge[p[node]^1].to;

}

return ret;

}

bool check()

{

For(i,0,N-1) if(imp[i]) if(edge[imp[i]].flow) return false;

return true;

}

int main()

{

init();

S=source_,T=sink_;

ISAP();

// printf("%d\n",ISAP());

if(!check())

{

puts("-1");

return 0;

}

S=source,T=sink;

printf("%d\n",ISAP()*3);

return 0;

}

Date Time

17/05/31 18:52

Author

OceanEye

Tags

有上下界网络流, 网络流, 费用流

Leave a Reply

有上下界网络流的学习笔记

Link1 Link2

BZOJ3876

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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 EE 40000
#define N 350
#define source 0
#define sink N-1
struct Tedge
{
	int to,flow,val;
}edge[EE];
#define E edge[i]
#define FLOW E.flow
#define TO E.to
#define VAL E.val
int fst[N],NXT[EE],e_tot;
int n;
void add_e(int from,int to,int flow,int val)
{
	static int &i=e_tot;
	TO=to; FLOW=flow; VAL=val; NXT[i]=fst[from]; fst[from]=i++;
	TO=from; FLOW=0; VAL=-val; NXT[i]=fst[to]; fst[to]=i++;
}
void init()
{
	int _,__,___;
	memset(fst,-1,sizeof(fst));
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(_);
		if(i!=1)add_e(i,1,INF,0);
		if(_==0) continue;
		add_e(i,sink,_,0);
		while(_--)
		{
			read(__); read(___);
			add_e(i,__,INF,___);
			add_e(source,__,1,___);
		}
	}
}

int S,T,ans;
int d[N],p[N];
bool inq[N];

void Augment()
{
//	puts("1");
	static int node,c,i;
	node=T; c=INF;
	while(node!=S)
	{
		i=p[node];
		c=min(FLOW,c);
		node=edge[i^1].to;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c; i^=1; FLOW+=c;
		node=TO;
	}
	ans+=c*d[T];
}

bool SPFA()
{
	static int Q[65540],x,i;
	static unsigned short int he=0,ta=0;
	memset(d,0x7f,sizeof(d));
	d[S]=0; inq[S]=true; Q[++he]=S;
	while(he!=ta)
	{
		x=Q[++ta]; inq[x]=0;
		for(i=fst[x];~i;i=NXT[i]) if(FLOW&&d[TO]>d[x]+VAL)
		{
			d[TO]=d[x]+VAL; p[TO]=i;
			if(!inq[TO]) inq[TO]=1,Q[++he]=TO;
		}
	}
	return d[T]<INF;
}

int main()
{
	init();
	S=source; T=sink;
	while(SPFA()) Augment();
	printf("%d",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#define ll long long

#define INF 1000000000

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

#define For(i,l,r) for(int i=l;i<=r;i++)

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 EE 40000

#define N 350

#define source 0

#define sink N-1

struct Tedge

{

int to,flow,val;

}edge[EE];

#define E edge[i]

#define FLOW E.flow

#define TO E.to

#define VAL E.val

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

int n;

void add_e(int from,int to,int flow,int val)

{

static int &i=e_tot;

TO=to; FLOW=flow; VAL=val; NXT[i]=fst[from]; fst[from]=i++;

TO=from; FLOW=0; VAL=-val; NXT[i]=fst[to]; fst[to]=i++;

}

void init()

{

int _,__,___;

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

read(n);

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

{

read(_);

if(i!=1)add_e(i,1,INF,0);

if(_==0) continue;

add_e(i,sink,_,0);

while(_--)

{

read(__); read(___);

add_e(i,__,INF,___);

add_e(source,__,1,___);

}

int S,T,ans;

int d[N],p[N];

bool inq[N];

void Augment()

{

// puts("1");

static int node,c,i;

node=T; c=INF;

while(node!=S)

{

i=p[node];

c=min(FLOW,c);

node=edge[i^1].to;

}

node=T;

while(node!=S)

{

i=p[node]; FLOW-=c; i^=1; FLOW+=c;

node=TO;

}

ans+=c*d[T];

}

bool SPFA()

{

static int Q[65540],x,i;

static unsigned short int he=0,ta=0;

memset(d,0x7f,sizeof(d));

d[S]=0; inq[S]=true; Q[++he]=S;

while(he!=ta)

{

x=Q[++ta]; inq[x]=0;

for(i=fst[x];~i;i=NXT[i]) if(FLOW&&d[TO]>d[x]+VAL)

{

d[TO]=d[x]+VAL; p[TO]=i;

if(!inq[TO]) inq[TO]=1,Q[++he]=TO;

}

return d[T]<INF;

}

int main()

{

init();

S=source; T=sink;

while(SPFA()) Augment();

printf("%d",ans);

return 0;

}

BZOJ2502

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define ll long long
#define INF 10000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)
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;
}
void cp(int &x,int y) { x>y?x=y:x=x; }
using namespace std;
#define EE 40000
#define N 150
#define source 0
#define sink (N-1)
#define sink_ (N-2)
#define source_ (N-3)
struct Tedge
{
	int to,flow;
}edge[EE];
int e_tot,fst[N],nxt[EE];
#define E edge[i]
#define FLOW E.flow
#define TO E.to
#define NXT nxt[i]
void add_e(int from,int to,int flow)
{
	static int &i=e_tot;
	FLOW=flow; TO=to; NXT=fst[from]; fst[from]=i++;
	FLOW=0; TO=from; NXT=fst[to]; fst[to]=i++;
}
int o[N],n;
void init()
{
	memset(fst,-1,sizeof(fst));
	int _,__;
	read(n);
	For(i,1,n)
	{
		add_e(source,i,INF);
		read(_); o[i]-=_;
		if(_==0) add_e(i,sink,INF);
		while(_--)
		{
			read(__);
			o[__]++;
			add_e(i,__,INF);
		}
	}
	For(i,1,n)
	{
		if(o[i]<0) add_e(i,sink_,-o[i]);
		else add_e(source_,i,o[i]);
	}
}

int m[N],d[N],p[N],cur[N],S,T;

bool bfs()
{
	static queue <int> Q; static int x,i;
	Q.push(T); d[T]=1;
	while(!Q.empty())
	{
		x=Q.front(); Q.pop(); m[d[x]]++;
		for(i=fst[x];~i;i=NXT) if((edge[i^1].flow)&&!d[TO])
		{
			d[TO]=d[x]+1;
			Q.push(TO);
		}
	}
	return d[S];
}

void Augment()
{
	static int node,c,i;
	node=T; c=INF;
	while(node!=S){
		i=p[node]; cp(c,FLOW);
		node=edge[i^1].to;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c; i^=1; FLOW+=c;
		node=TO;
	}
	return;
}

void ISAP()
{
	memset(m,0,sizeof(m)); memset(d,0,sizeof(d));
	int node=S,M,i; bool flag;
	For(i,0,N-1) cur[i]=fst[i];
	while(d[S]<=n+4)
	{
		if(node==T)
		{
			Augment();
			node=S;
		}
		flag=false;
		for(i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)
		{
			p[TO]=i;
			cur[node]=i;
			node=TO;
			flag=true;
			break;
		}
		if(flag) continue;
		if(!--m[d[node]]) return;
		M=N-1;
		for(cur[node]=i=fst[node];~i;i=NXT)
			if(FLOW) cp(M,d[TO]+1);
		m[d[node]=M]++;
		node=(node!=S?edge[p[node]^1].to:node);
	}
}

int main()
{
	freopen("BZOJ2502.in","r",stdin);
	init();
	S=source_; T=sink_;
	ISAP();
	add_e(sink,source,INF);
	ISAP();
	printf("%d\n",edge[e_tot-1].flow);
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define ll long long

#define INF 10000000

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

#define For(i,l,r) for(int i=l;i<=r;i++)

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;

}

void cp(int &x,int y) { x>y?x=y:x=x; }

using namespace std;

#define EE 40000

#define N 150

#define source 0

#define sink (N-1)

#define sink_ (N-2)

#define source_ (N-3)

struct Tedge

{

int to,flow;

}edge[EE];

int e_tot,fst[N],nxt[EE];

#define E edge[i]

#define FLOW E.flow

#define TO E.to

#define NXT nxt[i]

void add_e(int from,int to,int flow)

{

static int &i=e_tot;

FLOW=flow; TO=to; NXT=fst[from]; fst[from]=i++;

FLOW=0; TO=from; NXT=fst[to]; fst[to]=i++;

}

int o[N],n;

void init()

{

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

int _,__;

read(n);

For(i,1,n)

{

add_e(source,i,INF);

read(_); o[i]-=_;

if(_==0) add_e(i,sink,INF);

while(_--)

{

read(__);

o[__]++;

add_e(i,__,INF);

}

For(i,1,n)

{

if(o[i]<0) add_e(i,sink_,-o[i]);

else add_e(source_,i,o[i]);

}

int m[N],d[N],p[N],cur[N],S,T;

bool bfs()

{

static queue <int> Q; static int x,i;

Q.push(T); d[T]=1;

while(!Q.empty())

{

x=Q.front(); Q.pop(); m[d[x]]++;

for(i=fst[x];~i;i=NXT) if((edge[i^1].flow)&&!d[TO])

{

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

Q.push(TO);

}

return d[S];

}

void Augment()

{

static int node,c,i;

node=T; c=INF;

while(node!=S){

i=p[node]; cp(c,FLOW);

node=edge[i^1].to;

}

node=T;

while(node!=S)

{

i=p[node]; FLOW-=c; i^=1; FLOW+=c;

node=TO;

}

return;

}

void ISAP()

{

memset(m,0,sizeof(m)); memset(d,0,sizeof(d));

int node=S,M,i; bool flag;

For(i,0,N-1) cur[i]=fst[i];

while(d[S]<=n+4)

{

if(node==T)

{

Augment();

node=S;

}

flag=false;

for(i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW)

{

p[TO]=i;

cur[node]=i;

node=TO;

flag=true;

break;

}

if(flag) continue;

if(!--m[d[node]]) return;

M=N-1;

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

if(FLOW) cp(M,d[TO]+1);

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

node=(node!=S?edge[p[node]^1].to:node);

}

int main()

{

freopen("BZOJ2502.in","r",stdin);

init();

S=source_; T=sink_;

ISAP();

add_e(sink,source,INF);

ISAP();

printf("%d\n",edge[e_tot-1].flow);

return 0;

}

BZOJ2055

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

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;
}
void cp(int &x,int y) { x>y?x=y:x; }
using namespace std;
#define EE 80010
#define N 210
#define source 0
#define sink (N-1)
#define source_ (N-2)
#define sink_ (N-3)
#define calc(i) (i+n)
struct Tedge
{
	int to,flow,val;
}edge[EE];
int fst[N],nxt[EE],e_tot;
#define E edge[i]
#define FLOW E.flow
#define TO E.to
#define VAL E.val
#define NXT nxt[i]
void add_e(int from,int to,int flow,int val)
{
	static int &i=e_tot;
	TO=to; FLOW=flow; VAL=val; 
	NXT=fst[from]; fst[from]=e_tot++;
	TO=from; FLOW=0; VAL=-val;
	NXT=fst[to]; fst[to]=e_tot++;
}

int n,m,v[N];

void init()
{
	int _;
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	add_e(sink,source,m,0);
	for(int i=1;i<=n;i++)
	{
		add_e(source,i,INF,0);
		add_e(calc(i),sink,INF,0);
		read(_);
		add_e(source_,calc(i),_,0);
		add_e(i,sink_,_,0);
	}
	For(i,1,n-1)
		for(int j=i+1;j<=n;j++)
		{
			read(_); if(!~_) continue;
			add_e(calc(i),j,INF,_);
		}
}

int ans,d[N],p[N],S,T;
bool inq[N];

void Augment()
{
	static int node,c,i;
	node=T; c=INF;
	while(node!=S)
	{
		i=p[node];
		cp(c,FLOW); node=edge[i^1].to;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c; i^=1; FLOW+=c;
		node=TO;
	}
	ans+=c*d[T];
}

bool SPFA()
{
	static int Q[65540],i;
	static unsigned short int he=0,ta=0,x;
	memset(d,0x7f,sizeof(d));
	Q[++he]=S; d[S]=0;
	while(he!=ta)
	{
		x=Q[++ta]; inq[x]=false;
		for(i=fst[x];~i;i=NXT)
			if(FLOW&&d[TO]>d[x]+VAL)
			{
				d[TO]=d[x]+VAL; p[TO]=i;
				if(!inq[TO]) inq[TO]=true,Q[++he]=TO;
			}
	}
	if(d[T]>INF) return false;
	Augment();
	return true;
}

int main()
{
	init();
	S=source_; T=sink_;
	while(SPFA());
	printf("%d",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

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

#define For(i,l,r) for(int i=l;i<=r;i++)

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;

}

void cp(int &x,int y) { x>y?x=y:x; }

using namespace std;

#define EE 80010

#define N 210

#define source 0

#define sink (N-1)

#define source_ (N-2)

#define sink_ (N-3)

#define calc(i) (i+n)

struct Tedge

{

int to,flow,val;

}edge[EE];

int fst[N],nxt[EE],e_tot;

#define E edge[i]

#define FLOW E.flow

#define TO E.to

#define VAL E.val

#define NXT nxt[i]

void add_e(int from,int to,int flow,int val)

{

static int &i=e_tot;

TO=to; FLOW=flow; VAL=val;

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

TO=from; FLOW=0; VAL=-val;

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

}

int n,m,v[N];

void init()

{

int _;

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

read(n); read(m);

add_e(sink,source,m,0);

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

{

add_e(source,i,INF,0);

add_e(calc(i),sink,INF,0);

read(_);

add_e(source_,calc(i),_,0);

add_e(i,sink_,_,0);

}

For(i,1,n-1)

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

{

read(_); if(!~_) continue;

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

}

int ans,d[N],p[N],S,T;

bool inq[N];

void Augment()

{

static int node,c,i;

node=T; c=INF;

while(node!=S)

{

i=p[node];

cp(c,FLOW); node=edge[i^1].to;

}

node=T;

while(node!=S)

{

i=p[node]; FLOW-=c; i^=1; FLOW+=c;

node=TO;

}

ans+=c*d[T];

}

bool SPFA()

{

static int Q[65540],i;

static unsigned short int he=0,ta=0,x;

memset(d,0x7f,sizeof(d));

Q[++he]=S; d[S]=0;

while(he!=ta)

{

x=Q[++ta]; inq[x]=false;

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

if(FLOW&&d[TO]>d[x]+VAL)

{

d[TO]=d[x]+VAL; p[TO]=i;

if(!inq[TO]) inq[TO]=true,Q[++he]=TO;

}

if(d[T]>INF) return false;

Augment();

return true;

}

int main()

{

init();

S=source_; T=sink_;

while(SPFA());

printf("%d",ans);

return 0;

}

Date Time

17/05/9 21:15

Author

OceanEye

Tags

BZOJ, 最小割, 网络流

Leave a Reply

BZOJ4808

题目名字很有趣

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

网络流大法好，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;

}

Date Time

17/05/2 20:04

Author

OceanEye

Tags

最小割, 网络流

Leave a Reply

BZOJ1324

有些炸裂的题解

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

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

然后套最小点覆盖集用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;

}

Date Time

17/04/28 23:34

Author

OceanEye

Tags

最小割, 网络流

Leave a Reply

BZOJ1497

最小割

从源点向每个人连收益大小的边

人向站连大小为INF的边

站向汇连大小为成本的边

这个时候的割有三种情况：

1.把收益割掉了，此时支出>收入

2.把支出割掉了，此时支出<收入

3.支出和收入同时割掉了，支出=收入

总的答案就是sum-割

#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 400000
#define N 70050

struct Tedge
{
	int from,to,cap,flow;
}edge[E];

#define FROM edge[i].from
#define TO edge[i].to
#define FLO (edge[i].cap-edge[i].flow)

int e_tot,fst[N],NXT[E];
int n,m,tot;

void add_e(int _,int __,int ___)
{
	edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].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=___; edge[e_tot].flow=___;
	NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

#define calc(x) (x+m)
#define S 0
#define T N-1

void pre()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	int _,__,___;
	for(int i=1;i<=n;i++)
	{
		read(_);
		add_e(calc(i),T,_);
	}
	for(int i=1;i<=m;i++)
	{
		read(_); read(__); read(___);
		add_e(S,i,___);
		tot+=___;
		add_e(i,calc(__),INF);
		add_e(i,calc(_),INF);
	}
}


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

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

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

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

int main()
{
	pre();
	printf("%d\n",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 <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 400000

#define N 70050

struct Tedge

{

int from,to,cap,flow;

}edge[E];

#define FROM edge[i].from

#define TO edge[i].to

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

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

int n,m,tot;

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

{

edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].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=___; edge[e_tot].flow=___;

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

}

#define calc(x) (x+m)

#define S 0

#define T N-1

void pre()

{

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

read(n); read(m);

int _,__,___;

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

{

read(_);

add_e(calc(i),T,_);

}

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

{

read(_); read(__); read(___);

add_e(S,i,___);

tot+=___;

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

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

}

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

int Augment()

{

int node,cur,i;

cur=INF; node=T;

while(node!=S)

{

i=p[node];

cur=min(cur,FLO);

node=FROM;

}

node=T;

while(node!=S)

{

i=p[node];

edge[i].flow+=cur;

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

node=FROM;

}

return cur;

}

bool bfs()

{

int x;

dist[T]=1;

queue<int> Q; Q.push(T);

while(!Q.empty())

{

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

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

if(!FLO&&!dist[TO])

{

Q.push(TO);

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

}

return dist[S]!=0;

}

int ISAP()

{

int node=S,ret=0;

bool flag;

if(!bfs()) return false;

for(int i=0;i<N;i++)

{

cur[i]=fst[i];

if(dist[i]) cnt[dist[i]]++;

}

while(dist[S]<=n*2+2)

{

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)

{

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

node=TO;

flag=true;

break;

}

if(flag) continue;

int M=N-1;

cur[node]=fst[node];

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

{

if(!FLO) continue;

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

}

if(!--cnt[dist[node]]) break;

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

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

}

return ret;

}

int main()

{

pre();

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

return 0;

}

Date Time

17/04/8 00:03

Author

OceanEye

Tags

ISAP, 模板, 网络流, 费用流

Leave a Reply

BZOJ1834

嘛……几万年没好好写过网络流了……
gap优化真的强，把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……

/**************************************************************
    Problem: 1834
    User: OceanEYe
    Language: C++
    Result: Accepted
    Time:56 ms
    Memory:1948 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#define p(x) ('0'<=x&&x<='9')
#define INF 100000000
char cc; int C;
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;
}
template <class T>
void MN(T &x,T y) { x>y?x=y:x=x; }
 
using namespace std;
#define N 1005
#define E 10010
 
struct Tedge
{
    int from,to,cap,flow;
    int val;
}edge[E<<2];
#define TO edge[i].to
#define VAL edge[i].val
#define SIZ (edge[i].cap-edge[i].flow)
#define CAP edge[i].cap
int fst[N],NXT[E<<2],e_tot;
void add_e(int _,int __,int ___,int ____)
{
    edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].from=_; edge[e_tot].val=____;
    NXT[e_tot]=fst[_]; fst[_]=e_tot++;
    edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; edge[e_tot].from=__; edge[e_tot].val=-____;
    NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}
 
int S,T;
struct rec
{
    int a,b,c,d;
    rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {}
};
 
vector <rec> R; 
int n,m,k;
void init1()
{
    read(n); read(m); read(k);
    S=1; T=n;
    int _,__,___,____;
    memset(fst,-1,sizeof(fst));
    for(int i=1;i<=m;i++)
    {
        read(_); read(__); read(___); read(____);
        add_e(_,__,___,0);
        R.push_back(rec(_,__,___,____));
    }
}
//
bool vis[N];
int d[N],cnt[N],p[N],pre[N],ans;
int Augment()
{
    int r=T,c=INF,i;
    while(r!=S)
    {
        i=pre[r];
        MN(c,CAP-SIZ);
        r=TO;
    }
    r=T;
    while(r!=S)
    {
        i=pre[r];
        edge[i].flow-=c; edge[i^1].flow+=c;
        r=TO;
    }
    return c;
}
void ISAP()
{
    int node=S,c;
    for(int i=1;i<=n;i++) p[i]=fst[i];
    bool flag;
    while(d[S]<=n)
    {
        if(node==T)
        {
            ans+=Augment();
            node=S;
        }
        //solve
        flag=false;
        for(int i=p[node];~i;i=NXT[i])
        {
            if(d[TO]!=d[node]-1||SIZ==0) continue;
            p[node]=i;
            pre[TO]=i^1;
            node=TO;
            flag=true;
            break;
        }
        if(flag) continue;
        c=n+10;
        for(int i=fst[node];~i;i=NXT[i])
        {
            if(!SIZ) continue;
            MN(c,d[TO]+1);
        }
        if(--cnt[d[node]]==0)
        {
            printf("%d ",ans);
            return;
        }
        cnt[d[node]=c]++;
        p[node]=fst[node];
        if(node!=S)node=edge[pre[node]].to;
        //retreat
    }
    printf("%d ",ans);
}
queue<int> Q;
void bfs()
{
    int x;
    memset(vis,0,sizeof(vis));
    d[T]=1; Q.push(T); vis[T]^=1;
    while(!Q.empty())
    {
        x=Q.front(); Q.pop(); 
        cnt[d[x]]++;
        for(int i=fst[x];~i;i=NXT[i])
        {
            if(vis[TO]||SIZ) continue;
            d[TO]=d[x]+1;
            Q.push(TO);
            vis[TO]^=1;
        }
    }
}
//
int dis[N],cost;
void init2()
{
    int _,__,___,____;
    for(int i=0;i<m;i++)
    {
        _=R[i].a;
        __=R[i].b;
        ____=R[i].d;
        add_e(_,__,INF,____);
    }
}
int Augment2()
{
    int r=T,c=0,i;
    while(r!=S)
    {
        i=pre[r];
        edge[i].flow--; edge[i^1].flow++;
        c+=edge[i^1].val;
        r=TO;
    }
    return c;
}
void SPFA()
{
    memset(dis,0x7f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[S]=0; Q.push(S); vis[S]=true;
    int x,i;
    while(!Q.empty())
    {
        x=Q.front(); Q.pop(); vis[x]=false;
        for(i=fst[x];~i;i=NXT[i])
        {
            if(!SIZ) continue;
            if(dis[TO]<=dis[x]+VAL) continue;
            dis[TO]=dis[x]+VAL;
            pre[TO]=i^1;
            if(vis[TO]) continue;
            vis[TO]=true;
            Q.push(TO);
        }
    }
    cost+=Augment2();
}
//
int main()
{
    init1();
    bfs();
    ISAP();
    init2();
    for(int i=1;i<=k;i++) SPFA();
    printf("%d\n",cost);
    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

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

/**************************************************************

Problem: 1834

User: OceanEYe

Language: C++

Result: Accepted

Time:56 ms

Memory:1948 kb

****************************************************************/

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <queue>

#include <set>

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

#define INF 100000000

char cc; int C;

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;

}

template <class T>

void MN(T &x,T y) { x>y?x=y:x=x; }

using namespace std;

#define N 1005

#define E 10010

struct Tedge

{

int from,to,cap,flow;

int val;

}edge[E<<2];

#define TO edge[i].to

#define VAL edge[i].val

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

#define CAP edge[i].cap

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

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

{

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

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

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

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

}

int S,T;

struct rec

{

int a,b,c,d;

rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {}

};

vector <rec> R;

int n,m,k;

void init1()

{

read(n); read(m); read(k);

S=1; T=n;

int _,__,___,____;

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

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

{

read(_); read(__); read(___); read(____);

add_e(_,__,___,0);

R.push_back(rec(_,__,___,____));

}

bool vis[N];

int d[N],cnt[N],p[N],pre[N],ans;

int Augment()

{

int r=T,c=INF,i;

while(r!=S)

{

i=pre[r];

MN(c,CAP-SIZ);

r=TO;

}

r=T;

while(r!=S)

{

i=pre[r];

edge[i].flow-=c; edge[i^1].flow+=c;

r=TO;

}

return c;

}

void ISAP()

{

int node=S,c;

for(int i=1;i<=n;i++) p[i]=fst[i];

bool flag;

while(d[S]<=n)

{

if(node==T)

{

ans+=Augment();

node=S;

}

//solve

flag=false;

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

{

if(d[TO]!=d[node]-1||SIZ==0) continue;

p[node]=i;

pre[TO]=i^1;

node=TO;

flag=true;

break;

}

if(flag) continue;

c=n+10;

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

{

if(!SIZ) continue;

MN(c,d[TO]+1);

}

if(--cnt[d[node]]==0)

{

printf("%d ",ans);

return;

}

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

p[node]=fst[node];

if(node!=S)node=edge[pre[node]].to;

//retreat

}

printf("%d ",ans);

}

queue<int> Q;

void bfs()

{

int x;

memset(vis,0,sizeof(vis));

d[T]=1; Q.push(T); vis[T]^=1;

while(!Q.empty())

{

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

cnt[d[x]]++;

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

{

if(vis[TO]||SIZ) continue;

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

Q.push(TO);

vis[TO]^=1;

}

int dis[N],cost;

void init2()

{

int _,__,___,____;

for(int i=0;i<m;i++)

{

_=R[i].a;

__=R[i].b;

____=R[i].d;

add_e(_,__,INF,____);

}

int Augment2()

{

int r=T,c=0,i;

while(r!=S)

{

i=pre[r];

edge[i].flow--; edge[i^1].flow++;

c+=edge[i^1].val;

r=TO;

}

return c;

}

void SPFA()

{

memset(dis,0x7f,sizeof(dis));

memset(vis,false,sizeof(vis));

dis[S]=0; Q.push(S); vis[S]=true;

int x,i;

while(!Q.empty())

{

x=Q.front(); Q.pop(); vis[x]=false;

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

{

if(!SIZ) continue;

if(dis[TO]<=dis[x]+VAL) continue;

dis[TO]=dis[x]+VAL;

pre[TO]=i^1;

if(vis[TO]) continue;

vis[TO]=true;

Q.push(TO);

}

cost+=Augment2();

}

int main()

{

init1();

bfs();

ISAP();

init2();

for(int i=1;i<=k;i++) SPFA();

printf("%d\n",cost);

return 0;

}

OceanEye's Blog

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

Date Time

Author

Category

Tags

BZOJ3698

Description

Input

Output

Sample Input

Sample Output

HINT

Date Time

Author

Category

Tags

有上下界网络流的学习笔记

Date Time

Author

Category

Tags

BZOJ4808

Date Time

Author

Category

Tags

BZOJ1324

Date Time

Author

Category

Tags

BZOJ1497

Date Time

Author

Category

Tags

BZOJ1834