» USACO Gnarly Cow

March 2010
M	T	W	T	F	S	S
« Jan
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

USACO OPEN09 Gold Summary

May 27, 2009 — gnarlycow

Ski Lessons

动态规划

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

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

^?View Code CPP

/*
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: DP, Summary, USACO. No Comments »

USACO DEC08 Gold Summary

February 24, 2009 — gnarlycow

treat
不错的图论基础题。
本题中涉及到的图是一种特殊的有向图：每个结点都有且仅有一条出边。这样的有向图有一个很实用的性质：在每个连通分量中有且仅有一个环，而这个连通分量中的其它结点以树形连接到环上。对于环上的结点来说，题目要我们求的答案就是这个环的长度；而对于非环上的结点来说，答案就是它到环的距离再加上环的长度。这样，很容易想到一个线性算法解决问题。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: treat
*/
#include <cstdio>
#include <cstring>
 
int next[100001],p[100001],ans[100001],mark[100001];
 
int main()
{
	freopen("treat.in","r",stdin);
	freopen("treat.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",next+i);
	for(int i=1;i<=n;++i)
		if(ans[i]==0)
		{
			int j=i,k=0;
			for(;ans[j]==0;j=next[j])
			{
				mark[j]=k;
				p[k++]=j;
				ans[j]=-1;
			}
			if(ans[j]==-1)
			{
				for(int v=k-1;v>=mark[j];--v) ans[p[v]]=k-mark[j];
				for(int v=mark[j]-1;v>=0;--v) ans[p[v]]=k-v;
			}
			else
				for(int v=k-1;v>=0;--v) ans[p[v]]=ans[j]+k-v;
		}
	for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}

sec
字符串处理
输入数据给我们两组字符串A和B，我们只要先对A组中的字符串进行适当的预处理，就能快速找出B组中每一个字符串与A中多少个字符串相匹配。对于B组中每一个字符串s来说，我们需要知道A组中有多少个字符串是s的前缀和A组中有多少个字符串以s为前缀，一般情况下这两者之和即为所求结果。有一种特殊情况是A中有与s完全相同的字符串，这时注意不要重复计数。容易想到利用Trie树这种数据结构来解决问题，字典树可以很方便提供我们所需要的功能。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: sec
*/
#include <cstdio>
 
struct node
{
	int end,part;
	node *c[2];
	node():end(0),part(0)
	{
		c[0]=c[1]=NULL;
	}
} *root=new node();
 
int main()
{
	freopen("sec.in","r",stdin);
	freopen("sec.out","w",stdout);
	int m,n,k,v;
	scanf("%d %d",&m,&n);
	for(int i=0;i<m;++i)
	{
		node *t=root;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(!t->c[v]) t->c[v]=new node();
			t=t->c[v];
			++t->part;
		}
		++t->end;
	}
	for(int i=0;i<n;++i)
	{
		node *t=root;
		int ans=0;
		for(scanf("%d",&k);k;--k)
		{
			scanf("%d",&v);
			if(t)
			{
				ans+=t->end;
				t=t->c[v];
			}
		}
		if(t) ans+=t->part;
		printf("%d\n",ans);
	}
	return 0;
}

Posted in Gold Division, USACO. Tags: Gold, Summary, USACO. No Comments »

USACO NOV08 Gold Summary

February 23, 2009 — gnarlycow

mixup2
动态规划
假设p是n头牛所构成的集合的某个子集，last是p中的某头牛，f[p][last]表示集合p中的牛排队时满足last排在最后时的不同排队方案数。那么f[p][last]等于所有f[p-prev][prev]的和，其中prev为p中的另外一头牛并且满足prev和last两头牛的号码差的绝对值大于K。用二进制实现上述集合操作，时间复杂度O((2^n)*(n^2))。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: mixup2
*/
#include <cstdio>
#include <cstdlib>
 
int limit,d[16];
long long f[1<<16][16];
 
bool check(int a,int b)
{
	return abs(d[a]-d[b])>limit;
}
 
int main()
{
	freopen("mixup2.in","r",stdin);
	freopen("mixup2.out","w",stdout);
	int n;
	scanf("%d %d",&n,&limit);
	for(int i=0;i<n;++i) scanf("%d",d+i);
	for(int i=0;i<n;++i) f[1<<i][i]=1;
	for(int p=0;p<(1<<n);++p)
		for(int i=0;i<n;++i)
			if(p&(1<<i))
				for(int j=0;j<n;++j)
					if((p&(1<<j))&&check(i,j))
						f[p][i]+=f[p-(1<<i)][j];
	long long ans=0;
	for(int i=0;i<n;++i) ans+=f[(1<<n)-1][i];
	printf("%lld\n",ans);
	return 0;
}

cheer
图论，生成树变形
题目要求我们找出一颗生成树，并求出最小遍历代价。先考虑简单一些的问题：假设给定生成树和根，如何计算最小遍历代价。显然从根结点开始按照DFS顺序遍历代价最小，这时每条边都被经过两次，每个非根结点经过的次数等于它的度数，根结点比度数多一次。我们可以发现，如果不考虑根结点多出来的那一次花费，总花费实际上和根结点的选择无关，只和生成树有关。找代价最小的结点作为根结点把多余的那次花费算上，然后考虑找个代价最小的生成树。很容易想到最小生成树，其实这里无非就是多了个点代价而已。每个结点的经过次数等于度数，也就是与之相邻的边的数目，换个角度我们可以把代价放在边上。这样，让所有边的边权变为原来二倍再加上两个端点的代价，问题转化为标准最小生成树问题。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: cheer
*/
#include <iostream>
#include <algorithm>
 
using namespace std;
 
struct edge
{
	int a,b,w;
	bool operator<(const edge &other) const
	{
		return w<other.w;
	}
} e[100001];
int c[10001],f[10001],s[10001];
 
inline int getRoot(int v)
{
	while(f[v]!=v) v=f[v]=f[f[v]];
	return v;
}
 
bool merge(int a,int b)
{
	a=getRoot(a),b=getRoot(b);
	if(a==b) return true;
	if(s[a]<s[b]) s[b]+=s[a],f[a]=b;
	else s[a]+=s[b],f[b]=a;
	return false;
}
 
int main()
{
	freopen("cheer.in","r",stdin);
	freopen("cheer.out","w",stdout);
	int n,p,j=0,ans=INT_MAX;
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",c+i);
		ans=min(ans,c[i]);
	}
	for(int i=0;i<p;++i)
	{
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
		e[i].w=(e[i].w<<1)+c[e[i].a]+c[e[i].b];
	}
	sort(e,e+p);
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<n;++i)
	{
		for(;merge(e[j].a,e[j].b);++j);
		ans+=e[j].w;
	}
	printf("%d\n",ans);
	return 0;
}

lites
线段树
本题是线段树的基础题。线段树每个区间除了记录端点等必要信息外，还应根据需要记录一些额外信息，具体到本题就是每个区间中亮着的灯的数目。在取反操作中，如遇整个区间取反，只需在这个区间上加个取反标志，而不必立即修改子区间。为保证正确性，在以后的取反或询问操作中，如果遇到已经标记取反的区间，不要忘记把取反遗传到子区间。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: lites
*/
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n,sum[2000000];
bool rev[2000000];
 
void modify(int id,int L,int R,int a,int b)
{
	if(L==a&&R==b)
	{
		rev[id]=!rev[id];
		sum[id]=R-L+1-sum[id];
		return;
	}
	int M=(L+R)>>1;
	if(rev[id])
	{
		rev[id]=false;
		rev[id<<1]=!rev[id<<1];
		rev[(id<<1)+1]=!rev[(id<<1)+1];
		sum[id<<1]=M-L+1-sum[id<<1];
		sum[(id<<1)+1]=R-M-sum[(id<<1)+1];
	}
	if(b<=M) modify(id<<1,L,M,a,b);
	else if(a>M) modify((id<<1)+1,M+1,R,a,b);
	else
	{
		modify(id<<1,L,M,a,M);
		modify((id<<1)+1,M+1,R,M+1,b);
	}
	sum[id]=sum[id<<1]+sum[(id<<1)+1];
}
 
int getSum(int id,int L,int R,int a,int b)
{
	if(L==a&&R==b) return sum[id];
	int M=(L+R)>>1;
	if(rev[id])
	{
		rev[id]=false;
		rev[id<<1]=!rev[id<<1];
		rev[(id<<1)+1]=!rev[(id<<1)+1];
		sum[id<<1]=M-L+1-sum[id<<1];
		sum[(id<<1)+1]=R-M-sum[(id<<1)+1];
	}
	if(b<=M) return getSum(id<<1,L,M,a,b);
	else if(a>M) return getSum((id<<1)+1,M+1,R,a,b);
	else return getSum(id<<1,L,M,a,M)+getSum((id<<1)+1,M+1,R,M+1,b);
}
 
int main()
{
	freopen("lites.in","r",stdin);
	freopen("lites.out","w",stdout);
	int m,type,a,b;
	for(scanf("%d%d",&n,&m);m;--m)
	{
		scanf("%d%d%d",&type,&a,&b);
		if(type) printf("%d\n",getSum(1,1,n,a,b));
		else modify(1,1,n,a,b);
	}
	return 0;
}

Posted in Gold Division, USACO. Tags: Gold, Summary, USACO. No Comments »

USACO FEB09 Gold Summary

February 18, 2009 — gnarlycow

shuttle
贪心
本题看似动态规划题，但实际上存在如下贪心策略：将所有区间按照终点排序，优先让终点靠前的牛上车。直观上看，我们只需要让尽可能多的牛乘车，而不关心具体哪些牛乘车，让路途远的牛乘车和路途近的牛乘车对于我们来说是一样的。这样，终点靠前意味着早下车，可以让出座位留给后面的牛。本题数据量较大，可能需要借助一些高级数据结构来实现空座维护过程。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROB: shuttle
*/
#include <iostream>
#include <algorithm>
#include <map>
 
using namespace std;
 
struct segment
{
	int s,e,m;
	bool operator<(const segment &other) const
	{
		return s<other.s;
	}
} d[50005];
 
int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	int k,n,c,ans=0,cur=0;
	map <int,int> h;
	scanf("%d %d %d",&k,&n,&c);
	for(int i=0;i<k;++i) scanf("%d %d %d",&d[i].s,&d[i].e,&d[i].m);
	sort(d,d+k);
	for(int i=0;i<k;++i)
	{
		for(map <int,int>::iterator t=h.begin();t!=h.end()&&t->first<=d[i].s;h.erase(t++))
		{
			ans+=t->second;
			cur-=t->second;
		}
		h[d[i].e]+=d[i].m;
		cur+=d[i].m;
		map <int,int>::iterator t=h.end();
		for(--t;cur>c;)
			if(cur-t->second>c)
			{
				cur-=t->second;
				h.erase(t--);
			}
			else
			{
				t->second-=cur-c;
				cur=c;
			}
	}
	printf("%d\n",ans+cur);
	return 0;
}

stock
贪心+动态规划
在第3天购买某种股票然后在第5天卖，可以看成第3天购买，第4天卖出，第4天再购买，第5天再卖出。我们只关心低价购买，高价卖出，而股票的获利于你持股的时间没有关系，每天的买卖也没有限制，因此我们可以依次考虑每相邻的两天我们如何购买前一天的股票然后在后一天全部卖出。这样我们得到一个贪心算法，依次考虑每相邻两天，前一天买入后一天全部卖出所能得到的最大收益，而这正是个简单的背包问题：股票就是物品，花费就是前一天的价格，收益就是后一天的价格，背包就是资金。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROG: stock
*/
#include <iostream>
 
using namespace std;
 
int p[55][11],f[500005];
 
int main()
{
    freopen("stock.in","r",stdin);
    freopen("stock.out","w",stdout);
    int s,d,m;
    scanf("%d %d %d",&s,&d,&m);
    for(int i=0;i<s;++i)
        for(int j=0;j<d;++j)
            scanf("%d",&p[i][j]);
    for(int i=1;i<d;++i)
    {
        for(int j=0;j<=m;++j) f[j]=j;
		for(int j=0;j<s;++j)
			if(p[j][i]>p[j][i-1])
			{
				int prev=p[j][i-1],curr=p[j][i];
				for(int k=prev;k<=m;++k)
				{
					int t=f[k-prev]+curr;
					if(t>f[k]) f[k]=t;
				}
			}
		m=f[m];
    }
    printf("%d\n",m);
    return 0;
}

revamp
图论
按照如下方法构造新图：新图中结点用有序数对 $(i,j)$ 表示，其中 $1<=i<=n$ 且0<=j<=k。对于原图中的无向边 $(a,b)$ ，在新图中加入 $(a,u)$ 与 $(b,u)$ 之间的无向边 $(0<=u<=k)$ ，加入 $(a,u)$ 与 $(b,u+1)$ 之间的权为０的无向边 $(0<=u<k)$ 。除此之外，对于所有的 $u(0<=u<k)$ 加入 $(a,u)$ 与 $(a,u+1)$ 之间权为0的无向边。显然新图中点 $(1,0)$ 到 $(n,k)$ 的最短路径就是所求答案。我们可以使用Dijkstra和堆来快速求最短路径。

^?View Code CPP

/*
ID: lipeiqi1
LANG: C++
PROG: revamp
*/
#include <cstdio>
#include <cstring>
 
const int MAX_NODE_NUM=210012;
struct edge
{
	int v,w;
	edge *next;
	edge(int v,int w,edge *next):v(v),w(w),next(next) {}
} *e[10001];
struct THeap
{
	int v,d;
} heap[MAX_NODE_NUM];
int heapsize,k,n,pos[MAX_NODE_NUM];
 
void heapInit()
{
	heapsize=0;
	memset(pos,0,sizeof(pos));
}
 
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);
}
 
int dijkstra(int vstart)
{
	bool visited[MAX_NODE_NUM]={false};
	int pv,pdis,vend=n*(k+1);
	heapInit();
	heapUpdate(vstart,0);
	for(int i=0;i<vend;i++)
	{
		do
		{
			pv=heap[1].v,pdis=heap[1].d;
			deleteMin();
		} while(visited[pv]);
		if(pv==vend) return pdis;
		visited[pv]=true;
		int comp=(pv-1)/n;
		for(edge *t=e[pv-n*comp];t;t=t->next)
		{
			if(!visited[t->v+n*comp]) heapUpdate(t->v+n*comp,pdis+t->w);
			if(comp<k&&!visited[t->v+n*(comp+1)]) heapUpdate(t->v+n*(comp+1),pdis);
		}
		if(comp<k&&!visited[pv+n]) heapUpdate(pv+n,pdis);
	}
}
 
int main()
{
	freopen("revamp.in","r",stdin);
	freopen("revamp.out","w",stdout);
	int m,a,b,w;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;++i)
	{
		scanf("%d %d %d",&a,&b,&w);
		e[a]=new edge(b,w,e[a]);
		e[b]=new edge(a,w,e[b]);
	}
	printf("%d\n",dijkstra(1));
	return 0;
}

Posted in Gold Division, USACO. Tags: Gold, Summary, USACO. 3 Comments »

USACO JAN09 Gold Summary

February 9, 2009 — gnarlycow

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

^?View Code CPP

/*
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

/*
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

/*
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: Gold, Summary, USACO. 6 Comments »

Gnarly Cow We are continually faced with a series of great opportunities brilliantly disguised as insoluble problems.

Meta

Recent Posts

Spam Blocked

USACO OPEN09 Gold Summary

USACO DEC08 Gold Summary

USACO NOV08 Gold Summary

USACO FEB09 Gold Summary

USACO JAN09 Gold Summary

Tag Explosion

Best Friends

Recent Comments

Categories

Archives