USACO JAN09 Gold Summary

February 9, 2009 — gnarlycow

damage
构造
不错的图论基础题。首先，如果第i头牛报告它所在的结点未损坏但无法返回牛棚，那么所有地震后与i连通的结点都不能与牛棚连通，否则牛i就可以先到这个结点再返回牛棚。由于我们希望与牛棚不连通的结点数尽可能少，于是我们尽可能让结点与牛棚连通。如果第i头牛报告它所在的结点未损坏但无法返回牛棚，由于地震不破坏边，所以与结点i相邻的结点地震后一定仍能到达结点i，因此它们一定不与牛棚连通。除此之外，其它结点都可能与牛棚连通，这样对于每个报告，我们将与之相邻的结点标记为与牛棚不连通。最后从牛棚开始在剩余结点上floodfill，能到达的结点为真正能于牛棚连通的结点。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: damage
*/
#include <cstdio>
 
struct edge
{
	int v;
	edge *next;
	edge(int v,edge *next):v(v),next(next) {}
} *e[30003];
bool u[30003];
int ans;
 
void dfs(int v)
{
	if(u[v]) return;
	u[v]=true;
	--ans;
	for(edge *t=e[v];t;t=t->next) dfs(t->v);
}
 
int main()
{
	freopen("damage.in","r",stdin);
	freopen("damage.out","w",stdout);
	int p,c,n,a,b;
	scanf("%d %d %d",&p,&c,&n);
	for(int i=0;i<c;++i)
	{
		scanf("%d %d",&a,&b);
		e[a]=new edge(b,e[a]);
		e[b]=new edge(a,e[b]);
	}
	for(int i=0;i<n;++i)
	{
		scanf("%d",&b);
		for(edge *t=e[b];t;t=t->next) u[t->v]=true;
	}
	ans=p;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

baric

动态规划

f[i][j]表示前i个数中选出j个数作为子集并且第i个数一定入选子集的最小错误值，那么题中计算错误值的条件1对f[i][1]进行初始化，利用条件2进行状态转移求出f[i][j]，最后对于每个f[i][j]，将[i+1..n]造成的错误值考虑进来加到f[i][j]上去，枚举可求得错误值不超过限制的最小子集大小以及最小错误值。

?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

/*
ID: lipeiqi1
LANG: C++
PROB: baric
*/
#include <iostream>
 
using namespace std;
 
int d[101],f[101][101],s[101][101];
 
int main()
{
	freopen("baric.in","r",stdin);
	freopen("baric.out","w",stdout);
	int n,e;
	scanf("%d %d",&n,&e);
	for(int i=1;i<=n;++i) scanf("%d",d+i);
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
			f[i][1]+=abs(d[i]-d[j])<<1;
	for(int i=1;i<n;++i)
		for(int j=i+2;j<=n;++j)
			for(int k=i+1;k<j;++k)
				s[i][j]+=abs((d[k]<<1)-d[i]-d[j]);
	for(int i=2;i<=n;++i)
		for(int j=2;j<=i;++j)
		{
			f[i][j]=f[i-1][j-1];
			for(int k=i-2;k>0;--k) f[i][j]=min(f[i][j],f[k][j-1]+s[k][i]);
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			for(int k=i+1;k<=n;++k)
				f[i][j]+=abs(d[i]-d[k])<<1;
	int minNum=n,minErr=INT_MAX;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			if(f[i][j]<=e)
				if(j<minNum) minNum=j,minErr=f[i][j];
				else if(j==minNum) minErr=min(minErr,f[i][j]);
	printf("%d %d\n",minNum,minErr);
	return 0;
}

travel
图论综合题
由于题目保证从结点1到其它任何结点的最短路径唯一，结点1到其它结点的最短路径一定构成唯一的一棵最短路生成树。借助Dijkstra+普通二项堆可以在O(mlogm)的时间内构造最短路生成树。
接下来我们要做的就是求不经过最后一条边的次短路。从根(结点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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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

/*
ID: lipeiqi1
LANG: C++
PROG: travel
*/
#include <iostream>
#include <set>
 
using namespace std;
 
const int MAXN=100011;
struct edge
{
	int v,w;
	edge *next;
	edge(int v,int w,edge *next):v(v),w(w),next(next) {}
} *e[MAXN],*child[MAXN];
struct THeap
{
	int v,d;
} heap[MAXN];
int heapsize,k,n,timestamp,pos[MAXN],dis[MAXN],f[MAXN],num[MAXN],father[MAXN],ans[MAXN];
bool visited[MAXN];
multiset < pair<int,int> > d[MAXN];
 
inline int findRoot(int v)
{
	while(f[v]!=v) v=f[v]=f[f[v]];
	return v;
}
 
void unite(int x,int y)
{
	x=findRoot(x),y=findRoot(y);
	if(x==y) return;
	if(d[x].size()<d[y].size())
	{
		d[y].insert(d[x].begin(),d[x].end());
		d[x].clear();
		f[x]=y;
	}
	else
	{
		d[x].insert(d[y].begin(),d[y].end());
		d[y].clear();
		f[y]=x;
	}
}
 
void downMaintain(int k)
{
	int i=k;
	THeap x=heap[k];
	for(int j=k<<1;j<=heapsize;)
	{
		if(j<heapsize&&heap[j].d>heap[j+1].d) j++;
		if(x.d<=heap[j].d) break;
		heap[i]=heap[j];
		pos[heap[j].v]=i;
		i=j;
		j=i<<1;
	}
	heap[i]=x;
	pos[heap[i].v]=i;
}
 
void heapUpdate(int v,int dis)
{
	int i=pos[v];
	if(i&&heap[i].d<=dis) return;
	if(!i) i=++heapsize;
	for(;i!=1&&dis<heap[i>>1].d;i>>=1) heap[i]=heap[i>>1],pos[heap[i>>1].v]=i;
	heap[i].v=v;
	heap[i].d=dis;
	pos[v]=i;
}
 
void deleteMin()
{
	pos[heap[1].v]=0;
	heap[1]=heap[heapsize--];
	downMaintain(1);
}
 
void dijkstra(int vstart=1)
{
	int pv,pdis;
	heapUpdate(vstart,0);
	for(int i=0;i<n;i++)
	{
		do
		{
			pv=heap[1].v,pdis=heap[1].d;
			deleteMin();
		} while(visited[pv]);
		visited[pv]=true;
		dis[pv]=pdis;
		for(edge *t=e[pv];t;t=t->next)
			if(!visited[t->v])
				heapUpdate(t->v,pdis+t->w);
	}
}
 
void dfs(int v)
{
	num[v]=++timestamp;
	for(edge *t=child[v];t;t=t->next)
	{
		dfs(t->v);
		unite(v,t->v);
	}
	int c=findRoot(v);
	for(edge *t=e[v];t;t=t->next)
		if(t->v!=father[v])
		{
			if(!visited[t->v]||num[t->v]<num[v]) d[c].insert(make_pair(dis[v]+dis[t->v]+t->w,t->v)); 
			else
			{
				multiset<pair<int,int> >::iterator p=d[c].find(make_pair(dis[v]+dis[t->v]+t->w,v));
				if(p!=d[c].end()) d[c].erase(p);
			}
		}
	visited[v]=true;
	while(!d[c].empty()&&(visited[d[c].begin()->second]&&num[d[c].begin()->second]>num[v])) d[c].erase(d[c].begin());
	if(d[c].empty()) ans[v]=-1;
	else ans[v]=d[c].begin()->first;
}
 
int main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	int m,a,b,w;
	for(scanf("%d %d",&n,&m);m;--m)
	{
		scanf("%d %d %d",&a,&b,&w);
		e[a]=new edge(b,w,e[a]);
		e[b]=new edge(a,w,e[b]);
	}
	dijkstra();
	for(int i=1;i<=n;++i)
		for(edge *t=e[i];t;t=t->next)
			if(dis[i]+t->w==dis[t->v])
			{
				father[t->v]=i;
				child[i]=new edge(t->v,t->w,child[i]);
			}
	for(int i=1;i<=n;++i) f[i]=i;
	memset(visited,false,sizeof(visited));
	dfs(1);
	for(int i=2;i<=n;++i) printf("%d\n",ans[i]==-1?-1:ans[i]-dis[i]);
	return 0;
}
Posted in Gold Division, USACO. Tags: , , . 5 Comments »
«
»