BZOJ2597

@OceanEye8年前

05/29

21:50

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;

}

OceanEye's Blog

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

@OceanEye8年前

BZOJ2597

BZOJ2597

撤销评论

近期文章

标签