月度归档：2013年06月

[POJ 2482]

这题前面竟然是一封情信，字里行间都饱含作者的深情……于是又搜了下kinfkong，是位中大的前辈哦，都31岁结婚了。他博客里的文章也挺有意思的……

扯远了，回到题目本身吧。题面是：在二维平面上有N颗星星，各有一个亮度值c，问如果用一个长W宽H的矩形来括住某些星星，如何使窗口内星星亮度和最大。

说实在的，题目本身也出得非常巧妙。解题需要两次利用区间值求和的思想，即在[a,b]区间上加c，相当于在顺序遍历的基础上在a点加c，b+1点减c。第一次是在y轴方向上，若在(x,y)点处有一颗星星亮度为c，则在(x,y+H)上增加一颗亮度为-c的星星。这样，由y=0向上更新线段亮度值，便能将矩形区域求最大和转换成线段求最大和。第二次则是在x轴方向上的，对横坐标x亮度为c的星星，增加一颗x+W处亮度为-c的星星，这样便能进一步将线段最大和转换成点最大值。由此，便能利用线段树在每次插入星星的同时O(lgN)地更新最大亮度值了。

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

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star
{
	LL w,h,c;
	bool operator < (const star &p) const
	{
		if(h==p.h&&w==p.w) return c<p.c;
		if(h==p.h) return w<p.w;
		return h<p.h;
	}
}s[20001];

struct node
{
	LL sm,ld,rd,mx;
	bool b;
	node *l,*r;
}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)
{
	if(L==R)
	{
		e+=p->sm;
		p->sm=p->ld=p->rd=p->mx=e;
		return;
	}
	LL m=L+R>>1;
	if(p->b)
	{
		p->b=0;
		p->l=&mem[ml++];
		p->l->b=1;
		p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;
		p->r=&mem[ml++];
		p->r->b=1;
		p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;
	}
	if(i<=m) ins(i,e,L,m,p->l);
	else ins(i,e,m+1,R,p->r);
	p->sm=p->l->sm+p->r->sm;
	p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;
	p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;
	p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;
	p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;
}

int main()
{
	LL i,j,k,L,R;
	while(~scanf("%lld%lld%lld",&n,&W,&H))
	{
		ml=sl=mx=wl=0;
		L=0x7fffffff;
		R=0;
		root=&mem[ml++];
		root->sm=root->ld=root->rd=root->mx=0;
		root->b=1;
		while(n--)
		{
			scanf("%lld%lld%lld",&i,&j,&k);
			w[wl++]=i;
			L=i<L?i:L;
			R=(i+W)>R?(i+W):R;
			s[sl].w=i; s[sl].h=j; s[sl].c=k;
			sl++;
			s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;
			sl++;
		}
		sort(s,s+sl);
		sort(w,w+wl);
		for(i=j=1;i<wl;i++)
			if(w[i]!=w[j-1]) w[j++]=w[i];
		wl=j;
		for(i=0;i<sl;i++)
		{
			ins(s[i].w,s[i].c,L,R,root);
			ins(s[i].w+W,-s[i].c,L,R,root);
			mx=root->mx>mx?root->mx:mx;
		}
		printf("%lld\n",mx);
	}
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star

{

LL w,h,c;

bool operator < (const star &p) const

{

if(h==p.h&&w==p.w) return c<p.c;

if(h==p.h) return w<p.w;

return h<p.h;

}

}s[20001];

struct node

{

LL sm,ld,rd,mx;

bool b;

node *l,*r;

}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)

{

if(L==R)

{

e+=p->sm;

p->sm=p->ld=p->rd=p->mx=e;

return;

}

LL m=L+R>>1;

if(p->b)

{

p->b=0;

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

p->l->b=1;

p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;

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

p->r->b=1;

p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;

}

if(i<=m) ins(i,e,L,m,p->l);

else ins(i,e,m+1,R,p->r);

p->sm=p->l->sm+p->r->sm;

p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;

p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;

p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;

p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;

}

int main()

{

LL i,j,k,L,R;

while(~scanf("%lld%lld%lld",&n,&W,&H))

{

ml=sl=mx=wl=0;

L=0x7fffffff;

R=0;

root=&mem[ml++];

root->sm=root->ld=root->rd=root->mx=0;

root->b=1;

while(n--)

{

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

w[wl++]=i;

L=i<L?i:L;

R=(i+W)>R?(i+W):R;

s[sl].w=i; s[sl].h=j; s[sl].c=k;

sl++;

s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;

sl++;

}

sort(s,s+sl);

sort(w,w+wl);

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

if(w[i]!=w[j-1]) w[j++]=w[i];

wl=j;

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

{

ins(s[i].w,s[i].c,L,R,root);

ins(s[i].w+W,-s[i].c,L,R,root);

mx=root->mx>mx?root->mx:mx;

}

printf("%lld\n",mx);

}

return 0;

}

不过题目分类里写得这题属于“静态二叉检索树”。。。。这个暂时还没想出来该怎么写。。。

[POJ 2750]

发表回复

Potted Flower

分类表里最后一道线段树了。

题意大概是：有一个环，环上有N个整数，求在每次更新环上某个值后，环（除整个环外）任意弧上最大的整数和。

乍看下去，虽然提示是用线段树，但还是想了很久也没思路。再看了下输入规模，N最大10^5，更新次数M也是10^5，于是单次更新的处理时间只能是O(lgN)的。这样便能看出来是每次更新都在线段树上作O(lgN)深度的线段信息更新，再由根结点信息得到结果。

这里由左右子结点得到父结点信息的题推关系还是挺麻烦的……要考虑左连续区间最值和对应的最右元素位置，右连续区间最值和对应的最左元素位置，以及区间中任意子连续区间上的最值，再加上区间上全部整数和，总共是6个量。

这里要记录左右最值区间对应边界位置是因为，最后在根结点处计算时是可以将最右和最左看作连续的（环的性质），这样如果子结点上左右区间有重叠时，直接相加便会出错了，因此记录边界便能在仅当左右区间不重叠时才计算值。

另外这题要求不能取整个环上所有元素，因此实际上求的是最小弧，再用全部整数和减去最小值便能得到最大弧了。

#include<cstdio>
#include<cstring>

int n,m,d[100000],ml;

struct node
{
	int s,ld,rd,md,lr,rl;
	node *l,*r;
}mem[200000],*root;

void ins(int L,int R,node *p,int i=-1)
{
	int m=L+R>>1;
	if(L==R)
	{
		p->s=d[m];
		p->ld=p->rd=p->md=d[m];
		p->lr=p->rl=m;
		return;
	}
	if(i==-1)
	{
		p->l=&mem[ml++];
		p->r=&mem[ml++];
		ins(L,m,p->l);
		ins(m+1,R,p->r);
	}
	else if(i<=m) ins(L,m,p->l,i);
	else ins(m+1,R,p->r,i);
	p->s=p->l->s+p->r->s;
	if(p->l->ld<=p->l->s+p->r->ld)
	{
		p->ld=p->l->ld;
		p->lr=p->l->lr;
	}
	else
	{
		p->ld=p->l->s+p->r->ld;
		p->lr=p->r->lr;
	}
	if(p->r->rd<=p->r->s+p->l->rd)
	{
		p->rd=p->r->rd;
		p->rl=p->r->rl;
	}
	else
	{
		p->rd=p->r->s+p->l->rd;
		p->rl=p->l->rl;
	}
	p->md=p->l->rd+p->r->ld;
	p->md=p->md<p->l->md?p->md:p->l->md;
	p->md=p->md<p->r->md?p->md:p->r->md;
}

inline int calc(int i)
{
	ins(0,n-1,root,i);
	int e=root->md,m=n-1>>1;
	e=e<root->l->ld+root->r->rd?e:root->l->ld+root->r->rd;
	if(root->r->lr<root->r->rl)
		e=e<root->l->s+root->r->ld+root->r->rd?e:root->l->s+root->r->ld+root->r->rd;
	if(root->l->lr<root->l->rl)
		e=e<root->r->s+root->l->ld+root->l->rd?e:root->r->s+root->l->ld+root->l->rd;
	return root->s-e;
}

int main()
{
	int i,j;
	while(~scanf("%d",&n))
	{
		ml=0;
		root=&mem[ml++];
		for(i=0;i<n;i++) scanf("%d",&d[i]);
		scanf("%d",&m);
		ins(0,n-1,root);
		while(m--)
		{
			scanf("%d%d",&i,&j);
			d[i-1]=j;
			printf("%d\n",calc(i-1));
		}
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int n,m,d[100000],ml;

struct node

{

int s,ld,rd,md,lr,rl;

node *l,*r;

}mem[200000],*root;

void ins(int L,int R,node *p,int i=-1)

{

int m=L+R>>1;

if(L==R)

{

p->s=d[m];

p->ld=p->rd=p->md=d[m];

p->lr=p->rl=m;

return;

}

if(i==-1)

{

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

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

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

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

}

else if(i<=m) ins(L,m,p->l,i);

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

p->s=p->l->s+p->r->s;

if(p->l->ld<=p->l->s+p->r->ld)

{

p->ld=p->l->ld;

p->lr=p->l->lr;

}

else

{

p->ld=p->l->s+p->r->ld;

p->lr=p->r->lr;

}

if(p->r->rd<=p->r->s+p->l->rd)

{

p->rd=p->r->rd;

p->rl=p->r->rl;

}

else

{

p->rd=p->r->s+p->l->rd;

p->rl=p->l->rl;

}

p->md=p->l->rd+p->r->ld;

p->md=p->md<p->l->md?p->md:p->l->md;

p->md=p->md<p->r->md?p->md:p->r->md;

}

inline int calc(int i)

{

ins(0,n-1,root,i);

int e=root->md,m=n-1>>1;

e=e<root->l->ld+root->r->rd?e:root->l->ld+root->r->rd;

if(root->r->lr<root->r->rl)

e=e<root->l->s+root->r->ld+root->r->rd?e:root->l->s+root->r->ld+root->r->rd;

if(root->l->lr<root->l->rl)

e=e<root->r->s+root->l->ld+root->l->rd?e:root->r->s+root->l->ld+root->l->rd;

return root->s-e;

}

int main()

{

int i,j;

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

{

ml=0;

root=&mem[ml++];

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

scanf("%d",&m);

ins(0,n-1,root);

while(m--)

{

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

d[i-1]=j;

printf("%d\n",calc(i-1));

}

return 0;

}

[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差不多呢？实在不太明白…