分类目录归档：acm

[POJ 3678]

发表回复

Katu Puzzle

很神奇的2-SAT问题。找了一篇赵爽的《2-SAT解法浅析》。作者是高中生啊，查了下却发现是05年交大ACM总冠军队的成员……Orz

题目抽象出来后就不难做了，建一个含2*N个点的有向图，边由逻辑运算给出，边(u,v)表示选了u点则必须选v。编号为i的点对应图中i*2和i*2+1的两个点，分别表示i点取值为1、0。点A、B间由逻辑运算生成的边如下：

A & B == 1: 增加边(A*2+1,A*2)和(B*2+1,B*2);

A & B == 0: 增加边(A*2,B*2+1)和(B*2,A*2+1);

A | B == 1: 增加边(B*2+1,A*2)和(A*2+1,B*2);

A | B == 0: 增加边(A*2,A*2+1)和(B*2,B*2+1);

A ^ B == 1: 增加边(A*2,B*2+1)、(B*2+1,A*2)、(A*2+1,B*2)和(B*2,A*2+1);

A ^ B == 0: 增加边(A*2,B*2)、(B*2,A*2)、(A*2+1,B*2+1)和(B*2+1,A*2+1);

建好图后求强连通分量。最后判断是否对所有的i=0:N-1,是否有i*2和i*2+1不在同一强连通分量中，若成立则原问题有解，否则无解。

这里被 A & B == 1 和 A | B == 0 卡了一下……不可取的点直接引入必败边的做法非常巧妙……

同样分别使用了两次DFS和tarjan来求强连通分量，代码分别如下：

#include<cstdio>
#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000],v[2000],vl;
char s[4];
int xa,xb,c;

struct edge
{
	int j,p;
}e[4000000],er[4000000];

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

inline void adde()
{
	int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;
	if(s[0]=='A')
	{
		if(c==1)
		{
			e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;
			er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
		}
		else
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
	else if(s[0]=='O')
	{
		if(c==1)
		{
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
		}
		else
		{
			e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
		}
	}
	else
	{
		if(c==1)
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
		else
		{
			e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
}

void DFS(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		DFS(j);
	}
	v[vl++]=i;
}

void DFSr(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hdr[i];l!=-1;l=er[l].p)
	{
		j=er[l].j;
		if(b[j]) continue;
		un(i,j);
		DFSr(j);
	}
}

int chk()
{
	int i;
	for(i=0;i<n;i++)
		if(fi(i*2)==fi(i*2+1)) return 0;
	return 1;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		el=erl=vl=0;
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(f,-1,sizeof f);
		while(m--)
		{
			scanf("%d%d%d%s",&xa,&xb,&c,s);
			adde();
		}
		memset(b,0,sizeof b);
		for(i=0;i<2*n;i++)
			if(!b[i]) DFS(i);
		memset(b,0,sizeof b);
		for(i=vl-1;i>-1;i--)
			if(!b[v[i]]) DFSr(v[i]);
		puts(chk()?"YES":"NO");
	}
	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<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000],v[2000],vl;

char s[4];

int xa,xb,c;

struct edge

{

int j,p;

}e[4000000],er[4000000];

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

inline void adde()

{

int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;

if(s[0]=='A')

{

if(c==1)

{

e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;

er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

}

else

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else if(s[0]=='O')

{

if(c==1)

{

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

}

else

{

e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

}

else

{

if(c==1)

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else

{

e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

void DFS(int i)

{

int j,k,l;

b[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

DFS(j);

}

v[vl++]=i;

}

void DFSr(int i)

{

int j,k,l;

b[i]=1;

for(l=hdr[i];l!=-1;l=er[l].p)

{

j=er[l].j;

if(b[j]) continue;

un(i,j);

DFSr(j);

}

int chk()

{

int i;

for(i=0;i<n;i++)

if(fi(i*2)==fi(i*2+1)) return 0;

return 1;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

el=erl=vl=0;

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(f,-1,sizeof f);

while(m--)

{

scanf("%d%d%d%s",&xa,&xb,&c,s);

adde();

}

memset(b,0,sizeof b);

for(i=0;i<2*n;i++)

if(!b[i]) DFS(i);

memset(b,0,sizeof b);

for(i=vl-1;i>-1;i--)

if(!b[v[i]]) DFSr(v[i]);

puts(chk()?"YES":"NO");

}

return 0;

}

#include<cstdio>
#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000];
int st[2000],sl,stb[2000],low[2000];
char s[4];
int xa,xb,c;

struct edge
{
	int j,p;
}e[4000000],er[4000000];

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

inline void adde()
{
	int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;
	if(s[0]=='A')
	{
		if(c==1)
		{
			e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;
			er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
		}
		else
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
	else if(s[0]=='O')
	{
		if(c==1)
		{
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
		}
		else
		{
			e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
		}
	}
	else
	{
		if(c==1)
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
		else
		{
			e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
}

void tarjan(int i,int d)
{
	int j,k,l;
	b[i]=1;
	stb[i]=1;
	st[sl++]=i;
	low[i]=d;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(!b[j])
		{
			tarjan(j,d+1);
			low[i]=low[j]<low[i]?low[j]:low[i];
		}
		else if(stb[j]) low[i]=low[j]<low[i]?low[j]:low[i];
	}
	if(low[i]==d)
	{
		while(1)
		{
			sl--;
			un(i,st[sl]);
			if(st[sl]==i) break;
		}
	}
}

int chk()
{
	int i;
	for(i=0;i<n;i++)
		if(fi(i*2)==fi(i*2+1)) return 0;
	return 1;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		el=erl=0;
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(f,-1,sizeof f);
		while(m--)
		{
			scanf("%d%d%d%s",&xa,&xb,&c,s);
			adde();
		}
		sl=0;
		memset(b,0,sizeof b);
		for(i=0;i<2*n;i++)
		{
			memset(stb,0,sizeof stb);
			if(!b[i]) tarjan(i,1);
		}
		puts(chk()?"YES":"NO");
	}
	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

#include<cstdio>

#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000];

int st[2000],sl,stb[2000],low[2000];

char s[4];

int xa,xb,c;

struct edge

{

int j,p;

}e[4000000],er[4000000];

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

inline void adde()

{

int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;

if(s[0]=='A')

{

if(c==1)

{

e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;

er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

}

else

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else if(s[0]=='O')

{

if(c==1)

{

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

}

else

{

e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

}

else

{

if(c==1)

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else

{

e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

void tarjan(int i,int d)

{

int j,k,l;

b[i]=1;

stb[i]=1;

st[sl++]=i;

low[i]=d;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(!b[j])

{

tarjan(j,d+1);

low[i]=low[j]<low[i]?low[j]:low[i];

}

else if(stb[j]) low[i]=low[j]<low[i]?low[j]:low[i];

}

if(low[i]==d)

{

while(1)

{

sl--;

un(i,st[sl]);

if(st[sl]==i) break;

}

int chk()

{

int i;

for(i=0;i<n;i++)

if(fi(i*2)==fi(i*2+1)) return 0;

return 1;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

el=erl=0;

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(f,-1,sizeof f);

while(m--)

{

scanf("%d%d%d%s",&xa,&xb,&c,s);

adde();

}

sl=0;

memset(b,0,sizeof b);

for(i=0;i<2*n;i++)

{

memset(stb,0,sizeof stb);

if(!b[i]) tarjan(i,1);

}

puts(chk()?"YES":"NO");

}

return 0;

}

[codeforces] 杀入Div. 1!

发表回复

各种磕绊过后……终于我也Candidate Master啦！附送链接：eurce01

从#184开始……一场没算分，一场C题sort用了greater_equal导致TLE，一场电脑被A没做之后……终于我也Rating 1742啦！！

其实Div. 2的题还是挺轻松的……各种水题虐虐也能加分，不过也是#189开始才过了D题，结果直接Rank 17了。

但貌似这种难度的题才相当于Div. 1的B题啊……目测接下来还是狂跪的节奏……

无论如何还是bless自己一下吧……

[POJ 2886]

发表回复

Who Gets the Most Candies?

还是线段树……题目是N个人站成一个环进行N轮的筛人，每轮都筛走一个人，第i轮筛走的人得到f(i)颗糖，要求最先得到最多糖的人。第一个被筛的人为k，每次某人被筛，都会给出下一个被筛的人相对当前位置的偏移量（顺时针方向）ai，ai!=0且|ai|<10^8。其实知道要用线段树之后，题目就很简单了……k值的维护可以通过剩余人数n-i和a[i]求出，然后每轮筛去还在环中的第k个人即可，用线段树可以log(n)得到每轮被筛的人的编号。但这题竟然卡的是求f(i)。。。换了两种方法求f(i)都超时后便老老实实打表了。。。

#include<cstdio>

int n,k,d,di,a[500001],ml;
char s[500001][11];

struct node
{
	char b;
	int d;
	node *l,*r;
}mem[2000000],*root;

void init(int n)
{
	if(n<2) d=di=1;
	else if(n<4) d=di=2;
	else if(n<6) d=4,di=3;
	else if(n<12) d=6,di=4;
	else if(n<24) d=12,di=6;
	else if(n<36) d=24,di=8;
	else if(n<48) d=36,di=9;
	else if(n<60) d=48,di=10;
	else if(n<120) d=60,di=12;
	else if(n<180) d=120,di=16;
	else if(n<240) d=180,di=18;
	else if(n<360) d=240,di=20;
	else if(n<720) d=360,di=24;
	else if(n<840) d=720,di=30;
	else if(n<1260) d=840,di=32;
	else if(n<1680) d=1260,di=36;
	else if(n<2520) d=1680,di=40;
	else if(n<5040) d=2520,di=48;
	else if(n<7560) d=5040,di=60;
	else if(n<10080) d=7560,di=64;
	else if(n<15120) d=10080,di=72;
	else if(n<20160) d=15120,di=80;
	else if(n<25200) d=20160,di=84;
	else if(n<27720) d=25200,di=90;
	else if(n<45360) d=27720,di=96;
	else if(n<50400) d=45360,di=100;
	else if(n<55440) d=50400,di=108;
	else if(n<83160) d=55440,di=120;
	else if(n<110880) d=83160,di=128;
	else if(n<166320) d=110880,di=144;
	else if(n<221760) d=166320,di=160;
	else if(n<277200) d=221760,di=168;
	else if(n<332640) d=277200,di=180;
	else if(n<498960) d=332640,di=192;
	else d=498960,di=200;

}

inline int ins(int i)
{
	int L=0,R=n-1,m,e=k;
	node *p=root;
	while(1)
	{
		p->d++;
		m=L+R>>1;
		if(L==R) break;
		if(p->b)
		{
			p->b=0;
			p->l=&mem[ml++];
			p->l->b=1;
			p->l->d=0;
			p->r=&mem[ml++];
			p->r->b=1;
			p->r->d=0;
		}
		if(e<=m-L-p->l->d)
		{
			p=p->l;
			R=m;
		}
		else
		{
			e-=1+m-L-p->l->d;
			p=p->r;
			L=m+1;
		}
	}
	if(i<n-1)
	{
		if(a[m]>0) --k;
		a[m]%=n-1-i;
		a[m]+=n-1-i;
		k+=a[m];
		k%=n-1-i;
	}
	return m;
}

int main()
{
	int i,j;
	while(~scanf("%d%d",&n,&k))
	{
		init(n);
		ml=0;
		k--;
		root=&mem[ml++];
		root->b=1;
		root->d=0;
		for(i=0;i<n;i++) scanf("%s%d",s[i],&a[i]);
		for(i=0;i<d;i++) j=ins(i);
		printf("%s %d\n",s[j],di);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include<cstdio>

int n,k,d,di,a[500001],ml;

char s[500001][11];

struct node

{

char b;

int d;

node *l,*r;

}mem[2000000],*root;

void init(int n)

{

if(n<2) d=di=1;

else if(n<4) d=di=2;

else if(n<6) d=4,di=3;

else if(n<12) d=6,di=4;

else if(n<24) d=12,di=6;

else if(n<36) d=24,di=8;

else if(n<48) d=36,di=9;

else if(n<60) d=48,di=10;

else if(n<120) d=60,di=12;

else if(n<180) d=120,di=16;

else if(n<240) d=180,di=18;

else if(n<360) d=240,di=20;

else if(n<720) d=360,di=24;

else if(n<840) d=720,di=30;

else if(n<1260) d=840,di=32;

else if(n<1680) d=1260,di=36;

else if(n<2520) d=1680,di=40;

else if(n<5040) d=2520,di=48;

else if(n<7560) d=5040,di=60;

else if(n<10080) d=7560,di=64;

else if(n<15120) d=10080,di=72;

else if(n<20160) d=15120,di=80;

else if(n<25200) d=20160,di=84;

else if(n<27720) d=25200,di=90;

else if(n<45360) d=27720,di=96;

else if(n<50400) d=45360,di=100;

else if(n<55440) d=50400,di=108;

else if(n<83160) d=55440,di=120;

else if(n<110880) d=83160,di=128;

else if(n<166320) d=110880,di=144;

else if(n<221760) d=166320,di=160;

else if(n<277200) d=221760,di=168;

else if(n<332640) d=277200,di=180;

else if(n<498960) d=332640,di=192;

else d=498960,di=200;

}

inline int ins(int i)

{

int L=0,R=n-1,m,e=k;

node *p=root;

while(1)

{

p->d++;

m=L+R>>1;

if(L==R) break;

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->l->b=1;

p->l->d=0;

p->r=&mem[ml++];

p->r->b=1;

p->r->d=0;

}

if(e<=m-L-p->l->d)

{

p=p->l;

R=m;

}

else

{

e-=1+m-L-p->l->d;

p=p->r;

L=m+1;

}

if(i<n-1)

{

if(a[m]>0) --k;

a[m]%=n-1-i;

a[m]+=n-1-i;

k+=a[m];

k%=n-1-i;

}

return m;

}

int main()

{

int i,j;

while(~scanf("%d%d",&n,&k))

{

init(n);

ml=0;

k--;

root=&mem[ml++];

root->b=1;

root->d=0;

for(i=0;i<n;i++) scanf("%s%d",s[i],&a[i]);

for(i=0;i<d;i++) j=ins(i);

printf("%s %d\n",s[j],di);

}

return 0;

}

[POJ 2777]

发表回复

Count Color

依然是线段树，和POJ 2528比较类似，增加了查询某段区间内颜色种类数目的要求，这里由于颜色总数T值比较小(1<=T<=30)，因此可以用一个int以位相量的形式来表示某段区间包含的颜色情况。这里lazy tag用来表示结点的区间是否只含一种颜色。

#include<cstdio>

int l,t,o,ml;
char s[2];

struct node
{
	int c;
	char b;
	node *l,*r;
}mem[1000000],*root;

void ins(int l,int r,int L,int R,int k,node *p)
{
	if(l==L&&r==R)
	{
		p->b=1;
		p->c=k;
		return;
	}
	if(p->b)
	{
		p->b=0;
		if(!p->l)
		{
			p->l=&mem[ml++];
			p->l->l=p->l->r=0;
			p->r=&mem[ml++];
			p->r->l=p->r->r=0;
		}
		p->l->b=1;
		p->l->c=p->c;
		p->r->b=1;
		p->r->c=p->c;
	}
	int m=L+R>>1;
	if(r<=m) ins(l,r,L,m,k,p->l);
	else if(l>=m+1) ins(l,r,m+1,R,k,p->r);
	else
	{
		ins(l,m,L,m,k,p->l);
		ins(m+1,r,m+1,R,k,p->r);
	}
	p->c=p->l->c|p->r->c;
}

int ask(int l,int r,int L,int R,node *p)
{
	if(p->b||l==L&&r==R) return p->c;
	int m=L+R>>1;
	if(r<=m) return ask(l,r,L,m,p->l);
	if(l>=m+1) return ask(l,r,m+1,R,p->r);
	return ask(l,m,L,m,p->l)|ask(m+1,r,m+1,R,p->r);
}

int main()
{
	int i,j,k;
	while(~scanf("%d%d%d",&l,&t,&o))
	{
		ml=0;
		root=&mem[ml++];
		root->c=1;
		root->b=1;
		root->l=root->r=0;
		while(o--)
		{
			scanf("%s",s);
			if(s[0]=='C')
			{
				scanf("%d%d%d",&i,&j,&k);
				if(i>j) i^=j^=i^=j;
				--k;
				ins(i,j,1,l,1<<k,root);
			}
			else
			{
				scanf("%d%d",&i,&j);
				if(i>j) i^=j^=i^=j;
				k=ask(i,j,1,l,root);
				for(i=0;k;k>>=1) i+=k&1;
				printf("%d\n",i);
			}
		}
	}
	return 0;
}

#include<cstdio>

int l,t,o,ml;

char s[2];

struct node

{

int c;

char b;

node *l,*r;

}mem[1000000],*root;

void ins(int l,int r,int L,int R,int k,node *p)

{

if(l==L&&r==R)

{

p->b=1;

p->c=k;

return;

}

if(p->b)

{

p->b=0;

if(!p->l)

{

p->l=&mem[ml++];

p->l->l=p->l->r=0;

p->r=&mem[ml++];

p->r->l=p->r->r=0;

}

p->l->b=1;

p->l->c=p->c;

p->r->b=1;

p->r->c=p->c;

}

int m=L+R>>1;

if(r<=m) ins(l,r,L,m,k,p->l);

else if(l>=m+1) ins(l,r,m+1,R,k,p->r);

else

{

ins(l,m,L,m,k,p->l);

ins(m+1,r,m+1,R,k,p->r);

}

p->c=p->l->c|p->r->c;

}

int ask(int l,int r,int L,int R,node *p)

{

if(p->b||l==L&&r==R) return p->c;

int m=L+R>>1;

if(r<=m) return ask(l,r,L,m,p->l);

if(l>=m+1) return ask(l,r,m+1,R,p->r);

return ask(l,m,L,m,p->l)|ask(m+1,r,m+1,R,p->r);

}

int main()

{

int i,j,k;

while(~scanf("%d%d%d",&l,&t,&o))

{

ml=0;

root=&mem[ml++];

root->c=1;

root->b=1;

root->l=root->r=0;

while(o--)

{

scanf("%s",s);

if(s[0]=='C')

{

scanf("%d%d%d",&i,&j,&k);

if(i>j) i^=j^=i^=j;

--k;

ins(i,j,1,l,1<<k,root);

}

else

{

scanf("%d%d",&i,&j);

if(i>j) i^=j^=i^=j;

k=ask(i,j,1,l,root);

for(i=0;k;k>>=1) i+=k&1;

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

}

return 0;

}

用C++最快也只有266ms，但代码量只有第一名a3616001(79ms)的一半……这个可以用作自我安慰吗？

[POJ 2528]

发表回复

Mayor’s posters

很基础的线段树题目。在范围[1,10000000]内依次覆盖n段区间[ai,bi]，问最后未被完全覆盖的区间共有多少个。

做的时候参考了http://bbs.byr.cn/#!article/ACM_ICPC/71462。关键是对每个结点要设置tag记录是否为叶子，每次拆分时，叶子结点的值继承被拆结点的值，并将tag设置为1。插入每段区间时，根据区间和结点之间的上下界关系进行相应处理即可。最后全部插入完毕后，用DFS查找值有效的叶子结点种类数目：

#include<cstdio>
#include<cstring>

struct node
{
	char b;
	int d;
	node *l,*r;
}mem[10000000],*root;

int n,cnt,ml;
char c[10001];

void calc(int l,int r,int L,int R,node *p,int e)
{
	int j,k,m;
	if(l==L&&r==R)
	{
		p->b=1;
		p->d=e;
		return;
	}
	m=L+R>>1;
	if(p->b)
	{
		p->b=0;
		if(!p->l)
		{
			p->l=&mem[ml++];
			p->l->l=p->l->r=0;
		}
		p->l->b=1;
		p->l->d=p->d;
		if(!p->r)
		{
			p->r=&mem[ml++];
			p->r->l=p->r->r=0;
		}
		p->r->b=1;
		p->r->d=p->d;
	}
	if(r<=m) calc(l,r,L,m,p->l,e);
	else if(l>=m+1) calc(l,r,m+1,R,p->r,e);
	else
	{
		calc(l,m,L,m,p->l,e);
		calc(m+1,r,m+1,R,p->r,e);
	}
}

void DFS(node *p)
{
	if(p->b)
	{
		if(!c[p->d])
		{
			cnt++;
			c[p->d]=1;
		}
	}
	else
	{
		DFS(p->l);
		DFS(p->r);
	}
}

int main()
{
	int i,j,k;
	scanf("%*d");
	while(~scanf("%d",&n))
	{
		cnt=0;
		ml=0;
		root=&mem[ml++];
		root->b=1;
		root->d=0;
		root->l=root->r=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&j,&k);
			calc(j,k,1,100000000,root,i);
		}
		memset(c,0,sizeof c);
		c[0]=1;
		DFS(root);
		printf("%d\n",cnt);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

struct node

{

char b;

int d;

node *l,*r;

}mem[10000000],*root;

int n,cnt,ml;

char c[10001];

void calc(int l,int r,int L,int R,node *p,int e)

{

int j,k,m;

if(l==L&&r==R)

{

p->b=1;

p->d=e;

return;

}

m=L+R>>1;

if(p->b)

{

p->b=0;

if(!p->l)

{

p->l=&mem[ml++];

p->l->l=p->l->r=0;

}

p->l->b=1;

p->l->d=p->d;

if(!p->r)

{

p->r=&mem[ml++];

p->r->l=p->r->r=0;

}

p->r->b=1;

p->r->d=p->d;

}

if(r<=m) calc(l,r,L,m,p->l,e);

else if(l>=m+1) calc(l,r,m+1,R,p->r,e);

else

{

calc(l,m,L,m,p->l,e);

calc(m+1,r,m+1,R,p->r,e);

}

void DFS(node *p)

{

if(p->b)

{

if(!c[p->d])

{

cnt++;

c[p->d]=1;

}

else

{

DFS(p->l);

DFS(p->r);

}

int main()

{

int i,j,k;

scanf("%*d");

while(~scanf("%d",&n))

{

cnt=0;

ml=0;

root=&mem[ml++];

root->b=1;

root->d=0;

root->l=root->r=0;

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

{

scanf("%d%d",&j,&k);

calc(j,k,1,100000000,root,i);

}

memset(c,0,sizeof c);

c[0]=1;

DFS(root);

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

}

return 0;

}

[POJ 3308]

发表回复

Paratroopers

典型的最小割模型题目。做之前先读了国家集训队论文《最小割模型在信息学竞赛中的应用》。

题目大意是，有一个m*n的网格，m行和n列各对应一个权值。网格里面有l个点，如何在m行和n列中选择某些行列，使所有的点被覆盖，且使行列权值之积最小。

建图时S连所有行，E连所有列，行和列之间的边则对应原图的点且容量为无穷。这样便能应用最小割模型，得到的点集划分中割边必定为有穷边，且对应着原图中选中的行或列，使原图中每个点都能被覆盖（不能同时到S、E可达）。这里由于所求是作乘，将其取log，便转换成加法运算了。用EK求得最大流后，再从S点出发作DFS，就得到了实际的最小割方案，再依次检查遍历情况作乘即可。

不知为何c++竟然没有log2，CE了一次…T__T

#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

int t,m,n,hd[1002],el,b[1002],p[1002],S=0,E;
double c[1002][1002],d[1002][1002],mnf[1002];

struct edge
{
	int j,p;
}e[300000];

inline void adde(int i,int j,double k)
{
	c[i][j]=k;
	e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

void EK()
{
	int i,j,k,l;
	double f;
	while(1)
	{
		memset(b,0,sizeof b);
		mnf[S]=1e10;
		b[S]=1;
		queue<int>Q;
		Q.push(S);
		while(!Q.empty()&&!b[E])
		{
			i=Q.front(); Q.pop();
			for(l=hd[i];l!=-1;l=e[l].p)
			{
				j=e[l].j;
				if(b[j]||c[i][j]<1e-10) continue;
				mnf[j]=mnf[i]<c[i][j]?mnf[i]:c[i][j];
				p[j]=i;
				b[j]=1;
				Q.push(j);
			}
		}
		if(!b[E]) break;
		for(j=E;j!=S;j=p[j])
		{
			i=p[j];
			c[i][j]-=mnf[E];
			c[j][i]+=mnf[E];
		}
	}
}

void DFS(int i)
{
	int j,l;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]||c[i][j]<1e-10) continue;
		b[j]=1;
		DFS(j);
	}
}

int main()
{
	int i,j,k,l;
	double f;
	scanf("%*d");
	while(~scanf("%d%d%d",&m,&n,&l))
	{
		el=0;
		E=m+n+1;
		memset(hd,-1,sizeof hd);
		memset(c,0,sizeof c);
		for(i=1;i<=m;i++)
		{
			scanf("%lf",&f);
			adde(S,i,log(f));
			d[S][i]=f;
		}
		for(;i<=m+n;i++)
		{
			scanf("%lf",&f);
			adde(i,E,log(f));
			d[i][E]=f;
		}
		while(l--)
		{
			scanf("%d%d",&i,&j);
			adde(i,m+j,1e10);
		}
		EK();
		memset(b,0,sizeof b);
		b[S]=1;
		DFS(S);
		for(i=1,f=1;i<=m;i++)
		{
			if(!b[i]) f*=d[S][i];
		}
		for(;i<=m+n;i++)
		{
			if(b[i]) f*=d[i][E];
		}
		printf("%.4lf\n",f);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include<cmath>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int t,m,n,hd[1002],el,b[1002],p[1002],S=0,E;

double c[1002][1002],d[1002][1002],mnf[1002];

struct edge

{

int j,p;

}e[300000];

inline void adde(int i,int j,double k)

{

c[i][j]=k;

e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

void EK()

{

int i,j,k,l;

double f;

while(1)

{

memset(b,0,sizeof b);

mnf[S]=1e10;

b[S]=1;

queue<int>Q;

Q.push(S);

while(!Q.empty()&&!b[E])

{

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

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]||c[i][j]<1e-10) continue;

mnf[j]=mnf[i]<c[i][j]?mnf[i]:c[i][j];

p[j]=i;

b[j]=1;

Q.push(j);

}

if(!b[E]) break;

for(j=E;j!=S;j=p[j])

{

i=p[j];

c[i][j]-=mnf[E];

c[j][i]+=mnf[E];

}

void DFS(int i)

{

int j,l;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]||c[i][j]<1e-10) continue;

b[j]=1;

DFS(j);

}

int main()

{

int i,j,k,l;

double f;

scanf("%*d");

while(~scanf("%d%d%d",&m,&n,&l))

{

el=0;

E=m+n+1;

memset(hd,-1,sizeof hd);

memset(c,0,sizeof c);

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

{

scanf("%lf",&f);

adde(S,i,log(f));

d[S][i]=f;

}

for(;i<=m+n;i++)

{

scanf("%lf",&f);

adde(i,E,log(f));

d[i][E]=f;

}

while(l--)

{

scanf("%d%d",&i,&j);

adde(i,m+j,1e10);

}

EK();

memset(b,0,sizeof b);

b[S]=1;

DFS(S);

for(i=1,f=1;i<=m;i++)

{

if(!b[i]) f*=d[S][i];

}

for(;i<=m+n;i++)

{

if(b[i]) f*=d[i][E];

}

printf("%.4lf\n",f);

}

return 0;

}

[POJ 3352] and [POJ 3177]

发表回复

Road Construction

Redundant Paths

两题几乎是一样的，除了数据范围有些许差异。题目大意是，有一个连通的无向图，求至少需要添加多少条边，才能使得在图中任意移去一条边后仍然连通。

（又）WA了一天后发现：可以先缩点，将图转换成一颗树，然后求树上叶子结点的数目cnt，如果cnt==1输出0，否则需要增加的边数即为(cnt+1)/2。另外由于是无向图，不需要用入栈标记数组来判横向边，且已知图是连通的，DFS调用一次即可，略为简化了些代码。

具体实现如下：

#include<cstdio>
#include<cstring>

int n,r,el,eel,hd[5001],hde[5001],b[5001],cnt,f[5001];
int st[5001],sl;

struct edge
{
	int i,j,p;
}e[20000],ee[20000];

inline void adde(int i,int j)
{
	e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].i=j; e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

inline void addee(int i,int j)
{
	ee[eel].j=j; ee[eel].p=hde[i]; hde[i]=eel++;
	ee[eel].j=i; ee[eel].p=hde[j]; hde[j]=eel++;
}

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

void DFS(int i,int f,int d)
{
	int j,k,l;
	b[i]=d;
	st[sl++]=i;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(!b[j])
		{
			DFS(j,i,d+1);
			b[i]=b[j]<b[i]?b[j]:b[i];
		}
		else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];
	}
	if(b[i]==d)
	{
		while(st[--sl]!=i)
		{
			un(i,st[sl]);
		}
	}
}

void DFSe(int i,int f,int d)
{
	int j,k=0,l;
	b[i]=d;
	for(l=hde[i];l!=-1;l=ee[l].p)
	{
		j=ee[l].j;
		if(!b[j])
		{
			DFSe(j,i,d+1);
			b[i]=b[j]<b[i]?b[j]:b[i];
			if(!f)
			{
				if(l!=hde[i]) k=1;
			}
			else if(d<=b[j]) k=1;
		}
		else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];
	}
	if(!k) cnt++;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&r))
	{
		el=eel=0;
		cnt=0;
		memset(hd,-1,sizeof hd);
		memset(hde,-1,sizeof hde);
		memset(f,-1,sizeof f);
		while(r--)
		{
			scanf("%d%d",&i,&j);
			adde(i,j);
		}
		memset(b,0,sizeof b);
		sl=0;
		DFS(1,0,1);
		for(--el;el>-1;el-=2)
		{
			i=fi(e[el].i); j=fi(e[el].j);
			if(i!=j) addee(i,j);
		}
		memset(b,0,sizeof b);
		DFSe(fi(1),0,1);
		if(cnt<2)
		{
			puts("0");
			continue;
		}
		printf("%d\n",cnt+1>>1);
	}
	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

#include<cstdio>

#include<cstring>

int n,r,el,eel,hd[5001],hde[5001],b[5001],cnt,f[5001];

int st[5001],sl;

struct edge

{

int i,j,p;

}e[20000],ee[20000];

inline void adde(int i,int j)

{

e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].i=j; e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

inline void addee(int i,int j)

{

ee[eel].j=j; ee[eel].p=hde[i]; hde[i]=eel++;

ee[eel].j=i; ee[eel].p=hde[j]; hde[j]=eel++;

}

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

void DFS(int i,int f,int d)

{

int j,k,l;

b[i]=d;

st[sl++]=i;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(!b[j])

{

DFS(j,i,d+1);

b[i]=b[j]<b[i]?b[j]:b[i];

}

else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];

}

if(b[i]==d)

{

while(st[--sl]!=i)

{

un(i,st[sl]);

}

void DFSe(int i,int f,int d)

{

int j,k=0,l;

b[i]=d;

for(l=hde[i];l!=-1;l=ee[l].p)

{

j=ee[l].j;

if(!b[j])

{

DFSe(j,i,d+1);

b[i]=b[j]<b[i]?b[j]:b[i];

if(!f)

{

if(l!=hde[i]) k=1;

}

else if(d<=b[j]) k=1;

}

else if(j!=f) b[i]=b[j]<b[i]?b[j]:b[i];

}

if(!k) cnt++;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&r))

{

el=eel=0;

cnt=0;

memset(hd,-1,sizeof hd);

memset(hde,-1,sizeof hde);

memset(f,-1,sizeof f);

while(r--)

{

scanf("%d%d",&i,&j);

adde(i,j);

}

memset(b,0,sizeof b);

sl=0;

DFS(1,0,1);

for(--el;el>-1;el-=2)

{

i=fi(e[el].i); j=fi(e[el].j);

if(i!=j) addee(i,j);

}

memset(b,0,sizeof b);

DFSe(fi(1),0,1);

if(cnt<2)

{

puts("0");

continue;

}

printf("%d\n",cnt+1>>1);

}

return 0;

}

[POJ 2186]

发表回复

Popular Cows

题目大意：一个有向图，边(i,j)表示牛i认为牛j受欢迎，这种关系具有传递性。问：图中存在多少只牛被其他所有牛认为是受欢迎的？

很喜欢这种题……简洁的题面和清晰的题意，但足够一想想一天的。

思路是求强连通分支后缩点，再判断缩点后是否存在唯一出度数为0的点（也即最受欢迎牛群k），然后再判在反向图中，是否其余缩点从点k出发都可达。这里有个坑：如果总共只有一只牛，直接输出0。

具体实现上，分别尝试使用了CLRS上的两次DFS和tarjan来求强连通分支。另外，这题也是第一次写缩点，用了并查集，感觉有点累赘。

两次DFS：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

int n,m,ad[10001][10001],hd[10001],hdr[10001],a[10001],al,el,erl,f[10001],b[10001];

struct edge
{
	int i,j,p;
}e[50000],er[50000];

inline void adde(int i,int j)
{
	e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
}

inline void adder(int i,int j)
{
	er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++;
}

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

void DFS(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(!b[j]) DFS(j);
	}
	a[al++]=i;
}

void DFSr(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hdr[i];l!=-1;l=er[l].p)
	{
		j=er[l].j;
		if(!b[j])
		{
			un(i,j);
			DFSr(j);
		}
	}
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		memset(b,0,sizeof b);
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(f,-1,sizeof f);
		el=al=erl=0;
		while(m--)
		{
			scanf("%d%d",&i,&j);
			adde(i,j);
			adder(j,i);
		}
		if(n==1)
		{
			puts("0");
			continue;
		}
		for(i=1;i<=n;i++)
			if(!b[i]) DFS(i);
		memset(b,0,sizeof b);
		for(i=al-1;i>-1;i--)
			if(!b[a[i]]) DFSr(a[i]);
		memset(hdr,-1,sizeof hdr);
		erl=0;
		memset(b,0,sizeof b);
		for(l=0;l<el;l++)
		{
			i=fi(e[l].i); j=fi(e[l].j);
			if(i!=j)
			{
				adder(j,i);
				b[i]=1;
			}
		}
		queue<int>Q;
		for(l=1;l<=n;l++)
		{
			i=fi(l);
			if(i==l&&!b[i]) Q.push(i);
		}
		if(Q.empty()||Q.size()>1)
		{
			puts("0");
			continue;
		}
		k=Q.front();
		while(!Q.empty())
		{
			i=Q.front(); Q.pop();
			for(l=hdr[i];l!=-1;l=er[l].p)
			{
				j=er[l].j;
				if(b[j])
				{
					b[j]=0;
					Q.push(j);
				}
			}
		}
		for(i=1;i<=n&&!b[i];i++);
		if(i<=n) puts("0");
		else printf("%d\n",-f[k]);
	}
	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

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int n,m,ad[10001][10001],hd[10001],hdr[10001],a[10001],al,el,erl,f[10001],b[10001];

struct edge

{

int i,j,p;

}e[50000],er[50000];

inline void adde(int i,int j)

{

e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

}

inline void adder(int i,int j)

{

er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++;

}

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

void DFS(int i)

{

int j,k,l;

b[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(!b[j]) DFS(j);

}

a[al++]=i;

}

void DFSr(int i)

{

int j,k,l;

b[i]=1;

for(l=hdr[i];l!=-1;l=er[l].p)

{

j=er[l].j;

if(!b[j])

{

un(i,j);

DFSr(j);

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

memset(b,0,sizeof b);

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(f,-1,sizeof f);

el=al=erl=0;

while(m--)

{

scanf("%d%d",&i,&j);

adde(i,j);

adder(j,i);

}

if(n==1)

{

puts("0");

continue;

}

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

if(!b[i]) DFS(i);

memset(b,0,sizeof b);

for(i=al-1;i>-1;i--)

if(!b[a[i]]) DFSr(a[i]);

memset(hdr,-1,sizeof hdr);

erl=0;

memset(b,0,sizeof b);

for(l=0;l<el;l++)

{

i=fi(e[l].i); j=fi(e[l].j);

if(i!=j)

{

adder(j,i);

b[i]=1;

}

queue<int>Q;

for(l=1;l<=n;l++)

{

i=fi(l);

if(i==l&&!b[i]) Q.push(i);

}

if(Q.empty()||Q.size()>1)

{

puts("0");

continue;

}

k=Q.front();

while(!Q.empty())

{

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

for(l=hdr[i];l!=-1;l=er[l].p)

{

j=er[l].j;

if(b[j])

{

b[j]=0;

Q.push(j);

}

for(i=1;i<=n&&!b[i];i++);

if(i<=n) puts("0");

else printf("%d\n",-f[k]);

}

return 0;

}

tarjan（总感觉自己敲的东西有种山寨感？）：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

int n,m,hd[10001],hdr[10001],el,erl,dfn[10001],low[10001],b[10001],f[10001];
int st[10001],sl,tb[10001],d;

struct edge
{
	int i,j,p;
}e[50000],er[50000];

inline void adde(int i,int j)
{
	e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
}

inline void adder(int i,int j)
{
	er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++;
}

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

void tarjan(int i)
{
	int j,k,l;
	dfn[i]=low[i]=d++;
	st[sl++]=i;
	tb[i]=1;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(dfn[j]==-1)
		{
			tarjan(j);
			low[i]=low[j]<low[i]?low[j]:low[i];
		}
		else if(tb[j]) low[i]=low[j]<low[i]?low[j]:low[i];
	}
	if(dfn[i]==low[i])
	{
		while(1)
		{
			sl--;
			un(i,st[sl]);
			tb[st[sl]]=0;
			if(st[sl]==i) break;
		}
	}
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(b,0,sizeof b);
		memset(dfn,-1,sizeof dfn);
		memset(f,-1,sizeof f);
		memset(tb,0,sizeof tb);
		el=erl=sl=d=0;
		while(m--)
		{
			scanf("%d%d",&i,&j);
			adde(i,j);
		}
		if(n==1)
		{
			puts("0");
			continue;
		}
		for(i=1;i<=n;i++)
		{
			if(dfn[i]==-1) tarjan(i);
		}
		for(l=0;l<el;l++)
		{
			i=fi(e[l].i); j=fi(e[l].j);
			if(i!=j)
			{
				adder(j,i);
				b[i]=1;
			}
		}
		queue<int>Q;
		for(l=1;l<=n;l++)
		{
			i=fi(l);
			if(i==l&&!b[i]) Q.push(i);
		}
		if(Q.empty()||Q.size()>1)
		{
			puts("0");
			continue;
		}
		k=Q.front();
		while(!Q.empty())
		{
			i=Q.front(); Q.pop();
			for(l=hdr[i];l!=-1;l=er[l].p)
			{
				j=er[l].j;
				if(b[j])
				{
					b[j]=0;
					Q.push(j);
				}
			}
		}
		for(i=1;i<=n&&!b[i];i++);
		if(i<=n) puts("0");
		else printf("%d\n",-f[k]);
	}
	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<cstring>

#include<queue>

using namespace std;

int n,m,hd[10001],hdr[10001],el,erl,dfn[10001],low[10001],b[10001],f[10001];

int st[10001],sl,tb[10001],d;

struct edge

{

int i,j,p;

}e[50000],er[50000];

inline void adde(int i,int j)

{

e[el].i=i; e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

}

inline void adder(int i,int j)

{

er[erl].j=j; er[erl].p=hdr[i]; hdr[i]=erl++;

}

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

void tarjan(int i)

{

int j,k,l;

dfn[i]=low[i]=d++;

st[sl++]=i;

tb[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(dfn[j]==-1)

{

tarjan(j);

low[i]=low[j]<low[i]?low[j]:low[i];

}

else if(tb[j]) low[i]=low[j]<low[i]?low[j]:low[i];

}

if(dfn[i]==low[i])

{

while(1)

{

sl--;

un(i,st[sl]);

tb[st[sl]]=0;

if(st[sl]==i) break;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(b,0,sizeof b);

memset(dfn,-1,sizeof dfn);

memset(f,-1,sizeof f);

memset(tb,0,sizeof tb);

el=erl=sl=d=0;

while(m--)

{

scanf("%d%d",&i,&j);

adde(i,j);

}

if(n==1)

{

puts("0");

continue;

}

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

{

if(dfn[i]==-1) tarjan(i);

}

for(l=0;l<el;l++)

{

i=fi(e[l].i); j=fi(e[l].j);

if(i!=j)

{

adder(j,i);

b[i]=1;

}

queue<int>Q;

for(l=1;l<=n;l++)

{

i=fi(l);

if(i==l&&!b[i]) Q.push(i);

}

if(Q.empty()||Q.size()>1)

{

puts("0");

continue;

}

k=Q.front();

while(!Q.empty())

{

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

for(l=hdr[i];l!=-1;l=er[l].p)

{

j=er[l].j;

if(b[j])

{

b[j]=0;

Q.push(j);

}

for(i=1;i<=n&&!b[i];i++);

if(i<=n) puts("0");

else printf("%d\n",-f[k]);

}

return 0;

}

两种算法的耗时相近，但是两次DFS怎么会和一次DFS的tarjan差不多呢？实在不太明白…

[POJ 2942]

发表回复

Knights of the Round Table

最近的5天都在研究这一道题目，貌似效率有点低……不过还好最后AC了，作为充实blog的一点体会，也在此稍作记录吧。

一开始是写了一下穷搜，TLE后开始各种想……发现是知识储备不够，于是开始各种读解题报告，随即就读到了双连通分量，tarjan，二分图染色等一系列没听过的东西。BLOG的一个坏处是，知识点总是讲一点不讲一点，甚至有些是直接代码一帖完事。但这篇写得还是挺好的http://blog.csdn.net/lyy289065406/article/details/6756821。

稍微说点题外话，现在做题有个习惯是希望尽量把题目涉及的背景知识面都大致了解一下。之前也把CLRS看了一遍，就是希望自己的知识点不要有太明显的盲点，否则做题时效率实在太低了。但在做有些题的时候，往往认真读了相关定理及证明并实现了书上某个算法后，看题目的discuss却依然一大堆陌生名词。最明显的做网络流时，按照书上写的实现了Edmonds-Karp和Relabel-to-Front算法，也成功解出题目，以为可以和各路神牛做些基本沟通了，结果discuss里一堆dinic、sap什么什么的…………也不知道别人都看的是什么资料。这次这题也有这种感觉，而且真的是不喜欢那种遇到问题再去各种google的方式，感觉就是在打没准备的仗，而且长久下来，知识结构也会变得很零散……刚好这位博主有列出参考书目，也正是大名鼎鼎的黑书了。之前没有选择此书，一是觉得偏竞赛的书籍会较功利，而自己已经不可能全力准备什么比赛了，二是这本书稍微有点老了。但有书看总比一个个BLOG的翻要来得好，还是买回来了。

于是认真读了黑书P285页开始的部分，了解了DFS原来还有各种用法：求连通分量的割点、桥等等。作为对算法思想理解的验证，先A了1523，一道求割点对应分量数目的题目。然后又读了题解中用二分图性质判断奇圈的定理，便开始了各种构思算法实现。这里主要需要解决的问题是，如何保存用DFS找出的双连通分量。一开始我考虑的是在DFS的同时用栈记录当前遍历过的结点，在找到双连通分量时退栈输出结点，WA了数次后发现思路有误。关键在于像：

5 8

3 1

3 5

5 5

4 2

5 3

3 3

4 3

3 4

0 0

这样的数据，栈中会存在不属于当前双连通分量（属于父结点对应的双连通分量）但夹在本双连通分量结点间的结点（好罗嗦……）。于是只能用栈存边，这样出栈的时候，便肯定能得到属于本双连通分量的全部结点了。最后，再考虑了一下具体实现，总算是敲出了这题：

#include<cstdio>
#include<cstring>
using namespace std;

int n,m,d[1001][1001],hd[1001],a[1001],x[1001],el,ck[1001],temp[1001],b[1001],top;

struct edge		//边表
{
    int j,p;
} e[1000000];

struct stk		//边栈，记录当前双连通分量的一个环
{
    int i,j;
} st[1001];

inline void adde(int i,int j)
{
    e[el].j=j;
    e[el].p=hd[i];
    hd[i]=el++;
    e[el].j=i;
    e[el].p=hd[j];
    hd[j]=el++;
}

int CK(int i,int c)		//判断是否为二分图
{
    int j,k,l;
    ck[i]=c;
    for(l=hd[i]; l!=-1; l=e[l].p)
    {
        j=e[l].j;
        if(!b[j]) continue;
        if(ck[j]==-1)
        {
            if(!CK(j,c^1)) return 0;
        }
        else if(ck[j]!=c^1) return 0;
    }
    return 1;
}

void DFS(int i,int f,int d)		//DFS寻找双连通分量，并使用边栈来记录能表示双连通分量中的一个环
{
    int j,k,l;
    a[i]=d;
    for(l=hd[i]; l!=-1; l=e[l].p)
    {
        j=e[l].j;
        if(a[j]==-1)				//若子结点未访问，则记录边的同时深搜遍历
        {
            st[top].i=i;
            st[top].j=j;
            top++;
            DFS(j,i,d+1);
            a[i]=a[i]<a[j]?a[i]:a[j];		//更新最远祖先
            if(d==a[j])		//若为双连通分量，根据栈中的边来构建分量结点集合S，再判断是否为二分图
            {
            	memset(b,0,sizeof b);
            	k=0;
                while(1)
                {
                    --top;
                    temp[k++]=st[top].j;
                    b[st[top].j]=1;
                    if(st[top].i==i) break;
                }
                temp[k++]=i;
                b[i]=1;
                memset(ck,-1,sizeof ck);
                if(!CK(i,0))		//若不为二分图，则置分量中所有结点的标记位为1
                {
                    while(k) x[temp[--k]]=1;
                }
            }
            if(d<a[j]) --top;	//若(i,j)为桥，则令边栈栈顶出栈
        }
        else if(j!=f)		//更新最远祖先
        {
            a[i]=a[i]<a[j]?a[i]:a[j];
        }
    }
}

int main()
{
    int i,j,k,l;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        memset(d,0,sizeof d);
        memset(hd,-1,sizeof hd);
        memset(a,-1,sizeof a);
        memset(x,0,sizeof x);
        el=0;
        while(m--)
        {
            scanf("%d%d",&i,&j);
            d[i][j]=d[j][i]=1;
        }
        for(i=1; i<n; i++)
            for(j=i+1; j<=n; j++)
                if(!d[i][j]) adde(i,j);
        for(i=1,l=0; i<=n; i++)
        {
            top=0;
            if(a[i]==-1) DFS(i,0,1);
            if(!x[i]) l++;
        }
        printf("%d\n",l);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,d[1001][1001],hd[1001],a[1001],x[1001],el,ck[1001],temp[1001],b[1001],top;

struct edge //边表

{

int j,p;

} e[1000000];

struct stk //边栈，记录当前双连通分量的一个环

{

int i,j;

} st[1001];

inline void adde(int i,int j)

{

e[el].j=j;

e[el].p=hd[i];

hd[i]=el++;

e[el].j=i;

e[el].p=hd[j];

hd[j]=el++;

}

int CK(int i,int c) //判断是否为二分图

{

int j,k,l;

ck[i]=c;

for(l=hd[i]; l!=-1; l=e[l].p)

{

j=e[l].j;

if(!b[j]) continue;

if(ck[j]==-1)

{

if(!CK(j,c^1)) return 0;

}

else if(ck[j]!=c^1) return 0;

}

return 1;

}

void DFS(int i,int f,int d) //DFS寻找双连通分量，并使用边栈来记录能表示双连通分量中的一个环

{

int j,k,l;

a[i]=d;

for(l=hd[i]; l!=-1; l=e[l].p)

{

j=e[l].j;

if(a[j]==-1) //若子结点未访问，则记录边的同时深搜遍历

{

st[top].i=i;

st[top].j=j;

top++;

DFS(j,i,d+1);

a[i]=a[i]<a[j]?a[i]:a[j]; //更新最远祖先

if(d==a[j]) //若为双连通分量，根据栈中的边来构建分量结点集合S，再判断是否为二分图

{

memset(b,0,sizeof b);

k=0;

while(1)

{

--top;

temp[k++]=st[top].j;

b[st[top].j]=1;

if(st[top].i==i) break;

}

temp[k++]=i;

b[i]=1;

memset(ck,-1,sizeof ck);

if(!CK(i,0)) //若不为二分图，则置分量中所有结点的标记位为1

{

while(k) x[temp[--k]]=1;

}

if(d<a[j]) --top; //若(i,j)为桥，则令边栈栈顶出栈

}

else if(j!=f) //更新最远祖先

{

a[i]=a[i]<a[j]?a[i]:a[j];

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m)&&n)

{

memset(d,0,sizeof d);

memset(hd,-1,sizeof hd);

memset(a,-1,sizeof a);

memset(x,0,sizeof x);

el=0;

while(m--)

{

scanf("%d%d",&i,&j);

d[i][j]=d[j][i]=1;

}

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

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

if(!d[i][j]) adde(i,j);

for(i=1,l=0; i<=n; i++)

{

top=0;

if(a[i]==-1) DFS(i,0,1);

if(!x[i]) l++;

}

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

}

return 0;

}

虽然AC，但是g++跑了1100ms++，status上神牛们则是100ms左右……估计是递归验证二分图的那步效率太低了，但一时也想不到怎样改进比较好（而且实在不喜欢看别人的代码……）。以后有新思路了再来改进吧～