An Algorithm to the Maximum Single-Degree-Constrained Spanning Tree Problem

January 15, 2010 — gnarlycow

My Paper Download Link (Format: PDF)

My Photos

Posted in General. No Comments »

SGU 242 Student’s Morning

July 9, 2009 — gnarlycow

二分图匹配/网络流

把每个学校拆成两个点中间连一条容量下界为2的边，然后求可行流就行了。由于问题特殊，可以用二分图匹配来解决：把每个学校拆成两个点，如果一个学生愿意去一个学校，将这个学生和这个学校拆成的两个点各连一条边。利用匈牙利算法求二分图最大匹配，如果最大匹配数恰好为2k则有解，按照匹配方案输出即可，否则无解。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <iostream>
 
using namespace std;
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[222];
int match[222];
bool u[222];
 
bool findAugmentPath(int v)
{
	for(edge *t=e[v];t;t=t->next)
		if(!u[t->v])
		{
			u[t->v]=true;
			if(!match[t->v]||findAugmentPath(match[t->v]))
			{
				match[t->v]=v;
				return true;
			}
		}
	return false;
}
 
int main()
{
	int n,k,t,p;
	scanf("%d%d",&n,&k);
	if(k*2>n)
	{
		puts("NO");
		return 0;
	}
	for(int i=1;i<=n;++i)
		for(scanf("%d",&t);t;--t)
		{
			scanf("%d",&p);
			e[i]=new edge(p,e[i]);
			e[i]=new edge(k+p,e[i]);
		}
	int total=0;
	for(int i=1;i<=n;++i)
	{
		memset(u,false,sizeof(u));
		if(findAugmentPath(i)) ++total;
	}
	if(total==(k<<1))
	{
		puts("YES");
		for(int i=1;i<=k;++i) printf("2 %d %d\n",match[i],match[k+i]);
	}
	else puts("NO");
	return 0;
}
Posted in Uncategorized. No Comments »

USACO OPEN09 Gold Summary

May 27, 2009 — gnarlycow

Ski Lessons

动态规划

f[i][j]表示时刻i时滑雪能力为j的前提下，前i个时间单位里最多能滑多少次雪。我们采用向后递推法转移，有三种选择：(1)喝汽水；(2)参加时刻i开始的课程，能力值改变；(3)在能滑的雪坡中选择一个滑。

现在障碍在于雪坡数太多，每次都尝试所有能滑的雪坡转移代价太高。实际上我们并不需要尝试所有能滑的雪坡，因为滑雪用的时间越短越好，而滑任何雪坡效果都是一样的，能滑的雪坡之间没有优劣之分，所以要选择能滑的雪坡中用时最短的那个。通过预处理，可以在常数时间内获取这个信息。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/*
ID: lipeiqi1
LANG: C++
PROB: ski
*/
#include <iostream>
 
using namespace std;
 
struct tlesson
{
    int start,length,ability;
} lesson[10001];
int prev[101][101],mintime[101],f[10001][101];
 
bool operator<(const tlesson &a,const tlesson &b)
{
    return a.start<b.start;
}
 
void update(int &u,int v)
{
    if(u<v) u=v;
}
 
int main()
{
    freopen("ski.in","r",stdin);
    freopen("ski.out","w",stdout);
    int t,s,n,require,length;
    scanf("%d%d%d",&t,&s,&n);
    for(int i=0;i<s;++i) scanf("%d%d%d",&lesson[i].start,&lesson[i].length,&lesson[i].ability);
    sort(lesson,lesson+s);
    for(int i=1;i<101;++i) mintime[i]=INT_MAX;
    for(int i=0;i<n;++i)
    {
        scanf("%d%d",&require,&length);
        for(int j=require;j<101;++j) mintime[j]=min(mintime[j],length);
    }
    memset(f,-1,sizeof(f));
    f[0][1]=0;
    int cur=0,ans=-1;
    for(int i=0;i<=t;++i)
    {
        while(cur<s&&lesson[cur].start<i) ++cur;
        for(int j=1;j<101;++j)
            if(f[i][j]>-1)
            {
                update(ans,f[i][j]);
                if(i<t) update(f[i+1][j],f[i][j]);
                if(cur<s&&lesson[cur].start==i&&i+lesson[cur].length<=t) update(f[i+lesson[cur].length][lesson[cur].ability],f[i][j]);
                if(mintime[j]<INT_MAX&&i+mintime[j]<=t) update(f[i+mintime[j]][j],f[i][j]+1);
            }
    }
    printf("%d\n",ans);
    return 0;
}
Posted in Gold Division, USACO. Tags: , , . No Comments »

我十八岁了

May 21, 2009 — gnarlycow

法定上的成年意味着更多的权利和更多的责任。满十八岁后，我可以去申请支付宝卡通，参加一年一次的TopCoder Open……当然也必须为自己负责，为别人负责。

值得欣喜的是今天我的SAT成绩出来了，超出我的预期，算是一份美好的生日礼物吧。

Posted in 生活瞬间. Tags: . 3 Comments »

POI 2000 Skiers

May 19, 2009 — gnarlycow

贪心策略、深度优先搜索

网络流模型理论上可以解决此题，把除1和n以外的每个结点都拆成两个结点，中间用一条容量为1的边连接，结点1为源，结点n为汇求最大流。无奈本题数据规模较大，最多有5000个结点，而且边数未知。

注意到题目给出的图具有特殊的性质：边是按从东到西的顺序给出的，而且所有边不相交。这样我们可以采取如下贪心策略：用深度优先搜索从结点1出发找一条尽可能靠东（或尽可能靠西）的路径，让一个运动员沿此路径滑雪，把此路径上的除起点和终点外的所有结点从图中删去，然后重复此过程。这个策略显然正确，由于所有边都不相交，每次找最靠东（或最靠西）的路径可以给后面要找的路径腾出最大的空间。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
 
using namespace std;
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[5005];
int n;
bool u[5005];
 
bool dfs(int v)
{
	if(v==n) return true;
	u[v]=true;
	for(edge *t=e[v];t;t=t->next)
		if(!u[t->v]&&dfs(t->v))
			return true;
	return false;
}
 
int main()
{
	freopen("nar.in","r",stdin);
	freopen("nar.out","w",stdout);
	scanf("%d",&n);
	int t,v,ans=0;
	for(int i=1;i<n;++i)
		for(scanf("%d",&t);t;--t)
		{
			scanf("%d",&v);
			e[i]=new edge(v,e[i]);
		}
	for(edge *p=e[1];p;p=p->next)
		if(!u[p->v]&&dfs(p->v))
			++ans;
	printf("%d\n",ans);
	return 0;
}
Posted in POI. Tags: , . No Comments »

Anjuta1.2.4a的ppa

May 18, 2009 — gnarlycow

OIers都用Anjuta1.2.4a，可是在源中它早已被新版本所取代。事实上，绝大多数人都用新版的anjuta，只有像OIer这样需要对单文件代码编译和调试的人才会使用旧版。

我的同学Aron把anjuta1.2.4a搞进他的ppa里面了，从此我们可以用源安装并更新这个旧版本的anjuta。

添加PPA的方法：
1.先导入密钥以验证签名，在终端里输入这条命令：
sudo apt-key adv –recv-keys –keyserver keyserver.ubuntu.com DDA4DB69
2.然后是在软件包管理器的“设置”->“软件库”里面，找到“第三方软件”->“添加”相应apt行：
Ubuntu 9.10：
deb http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu karmic main
deb-src http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu karmic main
Ubuntu 9.04：
deb http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu jaunty main
deb-src http://ppa.launchpad.net/happyaron/anjuta-old/ubuntu jaunty main
确定后点“刷新”或sudo apt-get update更新软件包列表，这样就可以进行安装或者更新了。软件包名称为anjuta-old和anjuta-old-common。

Posted in Software. Tags: , , , . 3 Comments »

POI 1999 Water

May 18, 2009 — gnarlycow

优先队列

注意到边界上的格子一定不能存水，否则会流到外面去。现在考虑与边界相邻的格子。注满水后，对于某个与边界相邻的格子来水，它的积水状态只与它自己的恶高度和相邻边界格子的最低高度有关。这样，我们可以取边界格子中高度最低的格子，然后来得到与之相邻的内部格子的水位。假设边界格子中高度最低的为格子(x,y)，那么对于(x,y)的任意一个相邻非边界格子(x’,y’)来说，只要h(x,y)>h(x’,y’)” />，格子(x’,y’)就会有高度为<img src=的积水，这时我们可以把h(x,y)-h(x',y')累加到答案中去，然后把h(x',y')赋为h(x,y)并把(x’,y’)看作边界格子。如果h(x,y)<=h(x',y')，我们可以直接把(x’,y’)看作边界格子。当处理完所有(x,y)的相邻非边界格子后，把(x,y)从边界格子中删去。重复这个过程，直至边界格子集合为空为止。显然，用一个小根堆来维护边界格子集合是在适合不过了。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <iostream>
 
using namespace std;
 
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool u[111][111];
int ans,heapsize,h[111][111];
struct node
{
	int x,y,v;
} heap[11111];
 
void insert(int x,int y,int v)
{
	node key={x,y,v};
	int p=++heapsize;
	while(p>1&&heap[p>>1].v>v)
	{
		heap[p]=heap[p>>1];
		p>>=1;
	}
	heap[p]=key;
}
 
void deleteMin()
{
	int p=1;
	while((p<<1)<heapsize)
	{
		int i=p<<1;
		if(i+1<heapsize&&heap[i+1].v<heap[i].v) ++i;
		if(heap[i].v<heap[heapsize].v)
		{
			heap[p]=heap[i];
			p=i;
		}
		else break;
	}
	heap[p]=heap[heapsize--];
}
 
int main()
{
	freopen("wod.in","r",stdin);
	freopen("wod.out","w",stdout);
	int r,c;
	scanf("%d%d",&r,&c);
	for(int i=0;i<r;++i)
		for(int j=0;j<c;++j)
			scanf("%d",&h[i][j]);
	for(int i=0;i<c;++i)
	{
		u[0][i]=u[r-1][i]=true;
		insert(0,i,h[0][i]);
		insert(r-1,i,h[r-1][i]);
	}
	for(int i=1;i+1<r;++i)
	{
		u[i][0]=u[i][c-1]=true;
		insert(i,0,h[i][0]);
		insert(i,c-1,h[i][c-1]);
	}
	while(heapsize)
	{
		int x=heap[1].x,y=heap[1].y;
		deleteMin();
		for(int i=0;i<4;++i)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>-1&&tx<r&&ty>-1&&ty<c&&!u[tx][ty])
			{
				u[tx][ty]=true;
				if(h[tx][ty]<h[x][y])
				{
					ans+=h[x][y]-h[tx][ty];
					h[tx][ty]=h[x][y];
				}
				insert(tx,ty,h[tx][ty]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 2003 Monkeys

May 18, 2009 — gnarlycow

并查集

这是一道很棒的并查集类问题，具有较高的思维难度。注意到题目中所描述的猴子的连接方式，有可能猴子a抓住猴子b的尾巴，也有可能b抓住a的尾巴，也有可能a和b互相抓住对方的尾巴。其实我们只关心两个猴子是否相连，以上三种情况都是猴子a和b相连。现在题目要求的就是每只猴子第一次直接或间接脱离猴子1的时间。看起来好像和并查集的操作是相反的，那我们就反过来求解。首先求出时刻m所有放手行为都执行后猴子们的连接情况，然后从时刻m往前反过来执行“抓尾巴”行为，这样问题转化为求每个猴子第一次直接或间接与猴子1相连的时刻。这正是并查集所支持的操作，只是每次将猴子1所在集合与其它集合合并时，需要把那个集合的所有猴子的答案都设置为这个时刻。我们可以另外对每个集合维护一个链表，包含这个集合的所有猴子，合并时将链表合并。这样总的时间复杂度不变，问题成功解决。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <iostream>
 
using namespace std;
 
struct node
{
	int v;
	node *next;
	node(int v,node *next):v(v),next(next) {}
} *first[200002],*last[200002];
int d[400004][2],holdOrig[200002][2],holdCur[200002][2],ans[200002],f[200002];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
void uniteAndUpdateAns(int a,int b,int moment)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(x==getRoot(1))
			for(node *t=first[y];t;t=t->next)
				ans[t->v]=moment;
		else if(y==getRoot(1))
			for(node *t=first[x];t;t=t->next)
				ans[t->v]=moment;
		f[x]=y;
		last[y]->next=first[x];
		last[y]=last[x];
	}
}
 
int main()
{
	int n,m;
	memset(ans,-1,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&holdOrig[i][0],&holdOrig[i][1]);
		holdCur[i][0]=holdOrig[i][0];
		holdCur[i][1]=holdOrig[i][1];
	}
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&d[i][0],&d[i][1]);
		--d[i][1];
		holdCur[d[i][0]][d[i][1]]=-1;
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		first[i]=last[i]=new node(i,NULL);
	}
	for(int i=1;i<=n;++i)
	{
		if(holdCur[i][0]>-1) unite(i,holdCur[i][0]);
		if(holdCur[i][1]>-1) unite(i,holdCur[i][1]);
	}
	for(int i=m-1;i>-1;--i)
		if(holdOrig[d[i][0]][d[i][1]]>-1)
			uniteAndUpdateAns(d[i][0],holdOrig[d[i][0]][d[i][1]],i);
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 1998 Word Equations

May 17, 2009 — gnarlycow

并查集

本题中不同的变量可以表示不同长度的01串，这给解题带来了麻烦。我们可以把所有长度为p的变量拆成p个长度为1的变量，以简化问题。这样，所有拆分后得到的变量都只能表示一个0或1。假设等号两边的长度都为L，如果把0和1本身也看成特殊的变量的话，等式告诉我们的就是L个相等关系，即某两个变量相等。用并查集维护这些相等关系：初始时每个变量自成一个集合，每遇到一个相等关系，把相等的变量所在集合合并。如果某一时刻0和1所在的集合被合并，则说明出现矛盾，输出0；否则，没有矛盾出现，假设最终除0和1所在集合外共有r个集合，则答案为2^{r}。

注意测试数据中存在展开后等式两边长度不等的情况。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
 
using namespace std;
 
char s1[10011],s2[10011];
int total,len[33],s[10011],f[10011],size[10011],ans[11111111];
 
int getRoot(int v)
{
	if(f[v]==v) return v;
	else return f[v]=getRoot(f[v]);
}
 
void unite(int a,int b)
{
	int x=getRoot(a),y=getRoot(b);
	if(x!=y)
	{
		if(size[x]<size[y])
		{
			size[x]+=size[y];
			f[y]=x;
		}
		else
		{
			size[y]+=size[x];
			f[x]=y;
		}
		--total;
	}
}
 
int main()
{
	freopen("row.in","r",stdin);
	freopen("row.out","w",stdout);
	int T;
	for(scanf("%d",&T);T;--T)
	{
		int num,l1,l2;
		scanf("%d",&num);
		for(int i=0;i<num;++i) scanf("%d",len+i);
		scanf("%d\n%s\n%d\n%s",&l1,s1,&l2,s2);
		for(int i=1;i<num;++i) len[i]+=len[i-1];
		for(int i=num;i>0;--i) len[i]=len[i-1]+2;
		len[0]=2;
		int top=0;
		for(int i=0;i<l1;++i)
			if(s1[i]>='a'&&s1[i]<='z')
				for(int j=len[s1[i]-'a'];j<len[s1[i]-'a'+1];++j)
					s[top++]=j;
			else s[top++]=s1[i]-'0';
		for(int i=0;i<10005;++i) f[i]=i,size[i]=1;
		int firstTop=top;
		top=0;
		total=len[num]-2;
		for(int i=0;i<l2;++i)
		{
			if(s2[i]>='a'&&s2[i]<='z')
				for(int j=len[s2[i]-'a'];j<len[s2[i]-'a'+1];++j)
					unite(s[top++],j);
			else unite(s[top++],s2[i]-'0');
		}
		if(getRoot(0)==getRoot(1)||top!=firstTop) puts("0");
		else
		{
			memset(ans,0,sizeof(ans));
			int m=1;
			ans[0]=1;
			for(;total;--total)
			{
				int x=0;
				for(int i=0;i<m;++i)
				{
					ans[i]=(ans[i]<<1)+x;
					if(ans[i]>9) x=1,ans[i]-=10;
					else x=0;
				}
				if(x) ans[m++]=1;
			}
			for(int i=m-1;i>=0;--i) putchar('0'+ans[i]);
			putchar('\n');
		}
	}
	return 0;
}
Posted in POI. Tags: , . No Comments »

POI 1999 Three-coloring of Binary Trees

May 17, 2009 — gnarlycow

树型动态规划

首先根据给出的先序遍历序列建树，然后用两遍树型动态规划求出最大和最小值。假设绿色用0表示，1、2表示另外两种颜色。fmax(v,c)表示以v为根的子树中根结点v的颜色为c时的绿色结点数最大值。当v为叶结点时，fmax(v,0)=1而fmax(v,1)=fmax(v,2)=0；当v为非叶结点时，我们要给v的孩子结点分配不同于c的颜色，并在所有方案中去最大值，还有不要忘记当c为0时把根结点v自己加进去。求最小值与之类似，只要把所有的max都变为min即可。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
 
using namespace std;
 
int m,p,num[10011],cleft[10011],cright[10011],f[10011][3];
char s[10011];
 
int max(int a,int b,int c)
{
	return max(max(a,b),c);
}
 
int min(int a,int b,int c)
{
	return min(min(a,b),c);
}
 
void buildTree()
{
	num[m]=s[p++]-'0';
	if(num[m]==1)
	{
		cleft[m]=m+1;
		cright[m]=-1;
		++m;
		buildTree();
		return;
	}
	if(num[m]==2)
	{
		int t=m;
		cleft[t]=m+1;
		++m;
		buildTree();
		cright[t]=m;
		buildTree();
		return;
	}
	if(num[m]==0) cleft[m]=cright[m++]=-1;
}
 
int getMax(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=max(getMax(cleft[v],(c+1)%3),getMax(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=max(getMax(cleft[v],(c+1)%3)+getMax(cright[v],(c+2)%3),getMax(cleft[v],(c+2)%3)+getMax(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int getMin(int v,int c)
{
	if(f[v][c]>-1) return f[v][c];
	int r=(c==0);
	if(num[v]==1) r+=min(getMin(cleft[v],(c+1)%3),getMin(cleft[v],(c+2)%3));
	else if(num[v]==2) r+=min(getMin(cleft[v],(c+1)%3)+getMin(cright[v],(c+2)%3),getMin(cleft[v],(c+2)%3)+getMin(cright[v],(c+1)%3));
	return f[v][c]=r;
}
 
int main()
{
	freopen("trot.in","r",stdin);
	freopen("trot.out","w",stdout);
	gets(s);
	buildTree();
	memset(f,-1,sizeof(f));
	printf("%d ",max(getMax(0,0),getMax(0,1),getMax(0,2)));
	memset(f,-1,sizeof(f));
	printf("%d\n",min(getMin(0,0),getMin(0,1),getMin(0,2)));
	return 0;
}
Posted in POI. Tags: , , . No Comments »
« Older posts