费用流 | OceanEye's Blog

@OceanEye7年前

05/31

18:52

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

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;

}

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

@OceanEye7年前

05/29

21:50

BZOJ2597

OceanEye 撰写神技巧竞赛图费用流无回复

T飞了……
前排膜拜PoPoQQQ大神的题解

反正我的SPFA费用流是T飞了……
估计因为不停的memset 一共 \( n^2 \) 次然后就炸了吧
:-(等我学个ZKW的姿势回来再切这道题

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define INF 100000000
#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>
inline 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;
}
#define ququq 100000
char bsd[ququq]; int last;
inline void output() { puts(bsd); }
inline void add(int x,char lc)
{
	static char c[12]; static int node;
	if(x==0)
	{
		bsd[last++]='0';bsd[last++]=lc;
		return;
	}
	node=0;
	while(x) c[node++]=x%10,x/=10;
	while(node) bsd[last++]=c[--node]+'0';
	bsd[last++]=lc;
}

using namespace std;
#define N 110
#define SIZ 10200
#define S 0
#define T 10199
struct Tedge
{
	int from,to,flow,val;
}edge[SIZ<<6];
#define E edge[i]
#define TO E.to
#define FROM E.from
#define FLOW E.flow
#define VAL E.val
int fst[SIZ],NXT[SIZ<<6],e_tot;
void add_e(int from,int to,int cap,int val)
{
	static int &i=e_tot;
	FROM=from; TO=to; FLOW=cap; VAL=val;
	NXT[e_tot]=fst[from]; fst[from]=e_tot++;
	FROM=to; TO=from; FLOW=0; VAL=val;
	NXT[e_tot]=fst[to]; fst[to]=e_tot++;
}

int mp[N][N],n,A_[N][N],ans[N][N];

int calc(int i,int j) { if(i>j) swap(i,j); return (i-1)*n+j; }
inline void init()
{
	memset(fst,-1,sizeof(fst));
	read(n);
	For(i,1,n)
		for(int j=1;j<=n;j++) read(mp[i][j]);
	For(i,1,n)
		for(int j=0;j<n-1;j++) add_e(S,i,1,j);
	For(i,1,n)
		for(int j=1;j<=n;j++)
		{
			if(i==j) continue;
			if(i<j)add_e(calc(i,j)+n,T,1,0);
			if(mp[i][j]==1||mp[i][j]==2)
			{
				add_e(j,calc(i,j)+n,1,0);
				A_[i][j]=e_tot-1;
			}
		}
}
int p[SIZ],dis[SIZ],ANS;
bool inq[SIZ];

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

void Augment()
{
	static int node,c,i;
	node=T; c=INF;
	while(node!=S)
	{
		i=p[node];
		cp(c,FLOW);
		node=FROM;
	}
	node=T;
	while(node!=S)
	{
		i=p[node]; FLOW-=c; i^=1; FLOW+=c;
		node=TO;
	}
	ANS-=c*dis[T];
}

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

int main()
{
	freopen("BZOJ2597.in","r",stdin);
	init();
	ANS=n*(n-1)*(n-2)/6;
	while(SPFA()) Augment();
	add(ANS,'\n');
	For(i,1,n)
		for(int j=1;j<=n;j++) add(!A_[i][j]||!edge[A_[i][j]].flow?0:1,j==n?'\n':' ');
	output();
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#define ll long long

#define INF 100000000

#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>

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

}

#define ququq 100000

char bsd[ququq]; int last;

inline void output() { puts(bsd); }

inline void add(int x,char lc)

{

static char c[12]; static int node;

if(x==0)

{

bsd[last++]='0';bsd[last++]=lc;

return;

}

node=0;

while(x) c[node++]=x%10,x/=10;

while(node) bsd[last++]=c[--node]+'0';

bsd[last++]=lc;

}

using namespace std;

#define N 110

#define SIZ 10200

#define S 0

#define T 10199

struct Tedge

{

int from,to,flow,val;

}edge[SIZ<<6];

#define E edge[i]

#define TO E.to

#define FROM E.from

#define FLOW E.flow

#define VAL E.val

int fst[SIZ],NXT[SIZ<<6],e_tot;

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

{

static int &i=e_tot;

FROM=from; TO=to; FLOW=cap; VAL=val;

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

FROM=to; TO=from; FLOW=0; VAL=val;

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

}

int mp[N][N],n,A_[N][N],ans[N][N];

int calc(int i,int j) { if(i>j) swap(i,j); return (i-1)*n+j; }

inline void init()

{

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

read(n);

For(i,1,n)

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

For(i,1,n)

for(int j=0;j<n-1;j++) add_e(S,i,1,j);

For(i,1,n)

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

{

if(i==j) continue;

if(i<j)add_e(calc(i,j)+n,T,1,0);

if(mp[i][j]==1||mp[i][j]==2)

{

add_e(j,calc(i,j)+n,1,0);

A_[i][j]=e_tot-1;

}

int p[SIZ],dis[SIZ],ANS;

bool inq[SIZ];

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

void Augment()

{

static int node,c,i;

node=T; c=INF;

while(node!=S)

{

i=p[node];

cp(c,FLOW);

node=FROM;

}

node=T;

while(node!=S)

{

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

node=TO;

}

ANS-=c*dis[T];

}

bool SPFA()

{

static int x,Q[65540],i;

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

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

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

while(he!=ta)

{

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

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

{

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

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

if(!inq[TO])

{

dis[TO]<dis[Q[ta+1]]?Q[ta--]=TO:Q[++he]=TO;

inq[TO]=true;

}

return (dis[T]>INF)?false:true;

}

int main()

{

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

init();

ANS=n*(n-1)*(n-2)/6;

while(SPFA()) Augment();

add(ANS,'\n');

For(i,1,n)

for(int j=1;j<=n;j++) add(!A_[i][j]||!edge[A_[i][j]].flow?0:1,j==n?'\n':' ');

output();

return 0;

}

BZOJ2597

@OceanEye7年前

04/8

00:03

BZOJ1834

OceanEye 撰写 ISAP 模板网络流费用流无回复

嘛……几万年没好好写过网络流了……
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

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

@OceanEye7年前

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

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

@OceanEye7年前

BZOJ2597

BZOJ2597

@OceanEye7年前

BZOJ1834

BZOJ1834

友情链接

近期文章

标签