hdoj3339——最短路+01背包

最短路+01背包,但还没完全想清楚。
在装入背包时是否有可能出现装入最优方案时impossible,但是选择一种次优方案却可以得到值?

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define maxe 10000000
#define inf 1000010
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
bool visit[maxn];
int n,m;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int dp[6000];
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int cnt=0;
		memset(head,-1,sizeof(head));
		scanf("%d %d",&n,&m);
		n++;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			a++;
			b++;
			edge[cnt].to=b;
			edge[cnt].w=w;
			edge[cnt].next=head[a];
			head[a]=cnt++;

			edge[cnt].to=a;
			edge[cnt].w=w;
			edge[cnt].next=head[b];
			head[b]=cnt++;
		}
		int pow[maxn];
		int V=0;
		for(i=1;i<=n-1;i++)
		{
			scanf("%d",&pow[i]);
			V+=pow[i];
		}
		dij(1);
		int len=0;
		for(i=2;i<=n;i++)
		{
			len+=dist[i];
			dist[i-1]=dist[i];
		}
		if(V&1)
			V/=2;
		else
			V=V/2-1;
		for(j=0;j<=V;j++)
			dp[j]=0;
		for(i=1;i<=n-1;i++)
			for(j=V;j>=0;j--)
			{
				if(j>=pow[i])
				{
					dp[j]=max(dp[j],dp[j-pow[i]]+dist[i]);
				
				}
			}
			int ans=len-dp[V];
			if(ans>=inf)
				printf("impossible\n");
			else
				printf("%d\n",ans);

		




		
	
	
	
	
	}

system("pause");
return 0;
}

hdoj2833——最短路加DP

这题思路网上而来。。但还是又不理解的地方。网上说可以一边dij,一边求出那些边在最短路中,不解中。。
dp[i][j]表示悟空到达i点,师傅到达j点时的最多公共点数.dp[i][j]=(i==j)+max{dp[i的前驱][j],dp[i][j的前驱]}
状态转移涉及的点都在最短路径上。(i都在悟空的最短路径上,j都在师傅的最短路径上)
*************************************************************
dist[i]+map[i][j]=dist[j]。若j在最短路上,那么i在最短路上。
如果点数很多,不能用邻接矩阵时,可以用邻接表存图做最短路,但是因为要记忆化dp,所以这个图要用反邻接表存一下,以方便dp转移。(普通的链式前向星中是无法知道一个点的前驱的)

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define inf 1000000000
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
int map[maxn][maxn];
int d1[maxn],d2[maxn];
bool visit[maxn];
int n,m;
int max(int a,int b)
{
	return a>b?a:b;
}
void dij(int s,int* dist)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=1;i<=n;i++)
		{
			int v=i;
			if(map[u][v]!=inf && !visit[v] && dist[v]>dist[u]+map[u][v])
			{
				dist[v]=dist[u]+map[u][v];
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int dp[maxn][maxn];
int DP(int a,int b)
{
	if(dp[a][b]!=-1)
		return dp[a][b];
	int i,j,v=0;
	for(i=1;i<=n;i++)
		if(i!=a && d1[i]+map[i][a]==d1[a])
			v=max(v,DP(i,b));
	for(i=1;i<=n;i++)
		if(i!=b && d2[i]+map[i][b]==d2[b])
			v=max(v,DP(a,i));
	if(a==b)
		v++;
	dp[a][b]=v;
	return dp[a][b];
}
int main()
{
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF && (n!=0 || m!=0))
	{
		memset(dp,-1,sizeof(dp));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(i==j)
					map[i][j]=0;
				else
					map[i][j]=inf;
			}
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			if(w<map[a][b])
				map[a][b]=map[b][a]=w;
		}
		int s1,e1,s2,e2;
		scanf("%d %d %d %d",&s1,&e1,&s2,&e2);
		dij(s1,d1);
		dij(s2,d2);
		if(s1!=s2)
			dp[s1][s2]=0;
		else
			dp[s1][s2]=1;
		int ans=DP(e1,e2);
		printf("%d\n",ans);



	
	}
return 0;
}


hdoj1598

明天好好理解一下这段代码。。写的一知半解。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define maxn 210
#define maxe 2010
#define inf 1000000000
using namespace std;
typedef struct Edge{
    int w;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int pre[maxn];
int outque[maxn];
bool inque[maxn];
int n,m;
bool spfa(int low,int high,int s,int t)
{
    int i;
    queue<int> q;
    memset(outque,0,sizeof(outque));
    memset(inque,0,sizeof(inque));
    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[s]=0;
    inque[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        inque[u]=0;
        outque[u]++;
        if(outque[u]>n-1) return false;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            int w=edge[i].w;
            if(w<low || w>high)
                continue;
            if(dist[v]>dist[u]+edge[i].w)
            {
                dist[v]=dist[u]+edge[i].w;
                if(v==t)
                    return true;
                if(!inque[v])
                {
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
    return false;
}

int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        int a,b;
        int cnt=0;
        int max=-1;
        int w[maxe];
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&w[i]);
            if(max<w[i])
                max=w[i];
            edge[cnt].w=w[i];
            edge[cnt].to=b;
            edge[cnt].next=head[a];
            head[a]=cnt++;

            edge[cnt].w=w[i];
            edge[cnt].to=a;
            edge[cnt].next=head[b];
            head[b]=cnt++;
        }
        int query;
        sort(w+1,w+1+m);
        scanf("%d",&query);
        for(i=1;i<=query;i++)
        {
            int start,end;
            scanf("%d %d",&start,&end);
            if(!spfa(0,max,start,end))
            {
                printf("-1\n");
                continue;

            }

            int l=0,r=max+1,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                bool flag=0;
                for(j=1;w[j]<=max-mid;j++)
                {
                    if(spfa(w[j],w[j]+mid,start,end))
                    {
                        flag=1;
                        break;
                    }

                }
                if(flag)
                {
                    r=mid;
                }
                else
                    l=mid+1;
            }
            printf("%d\n",l);



        }


    }
return 0;
}

hdoj1688——最短路及次短路长度及路径数

图中边权均>=1 ,所以可以在dij的过程中求出最短路径数量和次短路径数量。
这段代码可以作为边权>=1的图求最短路和次短路长度及路径数量的模版
注意理清这个过程:在这个过程中,由于dij的定标技术,所以和普通的dij一样,距离源点最短距离小的点会先被定标。所以一个点的最短路肯定比次短路先永久确定(显然,一个点的最短路肯定短于次短路)。

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1010
#define maxe 10010
#define inf 10000000
using namespace std;
typedef struct node{
	int dist,point;
	int flag;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn][2],pre[maxn][2];
int cnt[maxn][2];
bool visit[maxn][2];
int n,m;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
	{
		dist[i][0]=dist[i][1]=inf;
		cnt[i][0]=cnt[i][1]=0;
	}
	dist[s][0]=0;
	cnt[s][0]=1;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;sr.flag=0;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point,flag=x.flag;
		if(visit[u][flag]) continue;
		visit[u][flag]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int w=edge[i].w;
			if(!visit[v][0] && dist[u][flag]+w<dist[v][0])
			{
				if(dist[v][0]<dist[v][1])
				{
					dist[v][1]=dist[v][0];
					cnt[v][1]=cnt[v][0];
					dist[v][0]=dist[u][flag]+w;
					cnt[v][0]=cnt[u][flag];
					node tmp;
					tmp.dist=dist[v][0];tmp.flag=0;tmp.point=v;q.push(tmp);
					tmp.dist=dist[v][1];tmp.flag=1;tmp.point=v;q.push(tmp);
				}
				else//说明最短路未曾更新,是inf
				{
					dist[v][0]=dist[u][flag]+w;
					cnt[v][0]=cnt[u][flag];
					node tmp;
					tmp.dist=dist[v][0];tmp.flag=0;tmp.point=v;q.push(tmp);
				
				}
			}
			else if(!visit[v][0] && dist[u][flag]+w==dist[v][0])
				cnt[v][0]+=cnt[u][flag];
			else if(!visit[v][1] && dist[u][flag]+w<dist[v][1])
			{
				dist[v][1]=dist[u][flag]+w;
				cnt[v][1]=cnt[u][flag];
				node tmp;
				tmp.dist=dist[v][1];tmp.flag=1;tmp.point=v;q.push(tmp);
			}
			else if(!visit[v][1] && dist[u][flag]+w==dist[v][1])
				cnt[v][1]+=cnt[u][flag];
		}
	}
	return;
}
int main()
{
	int cas,i;
	scanf("%d",&cas);
	while(cas--)
	{
		memset(head,-1,sizeof(head));
		int count=0;
		scanf("%d %d",&n,&m);
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			edge[count].to=b;
			edge[count].w=w;
			edge[count].next=head[a];
			head[a]=count++;
		}
		int s,t;
		scanf("%d %d",&s,&t);
		dij(s);
		int ans=cnt[t][0];
		if(dist[t][1]==dist[t][0]+1)
			ans+=cnt[t][1];
		printf("%d\n",ans);


	}
system("pause");
return 0;
}

关于dij和spfa的同时求最短路条数的问题小结

记一下昨晚想了很久的问题,今天又问了下学长,应该不会有错了。结论:对于边权>=1的图,可以在dij的过程中求出最短路径数量,如果有重边,则要用邻接表。如果边权中有0则不行。而spfa则不能在其过程中求出最短路径数量。

更进一步的,dij可以加上一维,同时求出次短路及其路径数量。

其根本性原理在于dij的贪心过程导致松弛一个点的时候这个点必定已经永久定标,而一个点的最短路必定是由dist较小的点才可能松弛过来的。这样,可以放心的对当前未定标的点中dist最小的点永久定标,因为此时不可能存在从其他未定标的点松弛过来得到一条或更多最短路。而spfa则不同,它是动态的修标,点u更新了到v的最短路条数后,可能u还有一条经过很多点的最短路没有松弛到,这样对于点v,明显漏了路径数。如果像dij那样松弛的时候相等也更新(对spfa来说就是dist[v]==dist[u]+edge(u,v)时v入队),那么这样虽然可能在u的最短路全找到之后更新v,但是很明显此时对于v,重复计算了很多路径(cnt[v]本来就记录了u的最短路没找完全时的cnt[u],u的最短路找全后cnt[v]又加上了cnt[u],显然加多了,进一步的,之后可能还会重复计数(u点可能还会因为某个点而重复判作有更新而入队))。

简单的解释就是这样。希望以后回顾还能记得这些。。其实自己这次看最短路才算真正看懂,上面的思路也很简略,甚至没有写关键的几个点,但是很多东西往往只能意会,只有在自己大脑中才会清晰明了,写是写不出来的。说句实话,对于像dij、spfa这样的经典算法,不仔细推敲上两三天(指的是第2、3次看)是不会真的理解的(不理解的话就只能做做裸题了)。。至少对于我来说是这样。

与图论相关的国家集训队论文集合

徐静:《图论模型的建立与转化》
江鹏:《从一道题目的解法试谈网络流的构造与算法》
金恺:《浅谈网络流算法的应用》
孙方成:《偶图的算法及应用》
周文超:《树结构在程序设计中的运用》
刘才良:《平面图在信息学中的应用》
伍昱:《由对称性解2-SAT问题》
吴景岳:《最小生成树算法及其应用》
贝小辉:《浅析树的划分问题》
黄源河:《浅谈图论模型的建立与应用》
汪汀:《最小生成树问题的拓展》
肖天:《“分层图思想”及其在信息学竞赛中的应用》
栗师:《树的乐园——一些与树有关的题目》
任恺:《图论的基本思想及方法》
王俊:《浅析二分图匹配在信息学竞赛中的应用》
陈首元:《维护森林连通性——动态树》
冯威:《数与图的完美结合——浅析差分约束系统》
贾由:《由图论算法浅析算法优化》
余远铭:《最短路算法及其应用》
湖南 仇荣琦 欧拉回路性质与应用探究
湖南 袁昕颢 动态树及其应用
上海 王欣上 浅谈基于分层思想的网络流算法
//广东 陈启峰 Size Balanced Tree
湖南 郭华阳 RMQ与LCA问题
福建 胡伯涛 最小割模型在信息学竞赛中的应用
安徽 周 冬 生成树的计数及其应用
吕子鉷《浅谈最短径路问题中的分层思想》
漆子超 《分治算法在树的路径问题中的应用》
姜碧野 《SPFA算法的优化及应用》
附上99——09论文全集>点我下载

 

hdoj1599

这几天狂刷webdiy,做了很多题目却来不及发上来总结,不多很多都是以前知识点的复习,今天学了最小环。这个写一下重点。
floyd求最小环关键代码

for(k=1;k<=n;k++)
{
////////////////////////////////////////////////////////////////////////
	for(i=1;i<=k-1;i++)
		for(j=i+1;j<=k-1;j++)
			if(map[k][i]+dist[i][j]+map[j][k]<ans)
				ans=map[k][i]+dist[i][j]+map[j][k];
/////////////////////////////////////////////////////////////////////////
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(dist[i][k]+dist[k][j]<dist[i][j])
				dist[i][j]=dist[i][k]+dist[k][j];
		}
}

可见,与普通floyd的唯一不同点就是斜线包含部分。以下称这部分代码为*代码
map[k][i]+dist[i][j]+map[j][k]代码求的是以k为环中最大编号的环的长度,其中i与j是与k点直接相连的点(这里没有判断i、j是否直接与k相邻,但可以保证正确,因为不相邻的点之间距离为inf,加起来之后肯定不是最小环,对结果无影响)。
为什么*代码要放在在前面
当要执行*代码时最外层循环已经执行了k-1次,这表示对于图中任意两点i、j,已经在它们之间插入了1——k-1这些点(用1——k-1这些点松弛过),所以此时任意两点i、j之间的最短路只可能经过了1——k-1这些点,不会经过k点,这样就保证了map[k][i]-dist[i][j]-map[j][k]形成的是环,也就是说没有重复经过同一点。
为什么*代码中i、j两层循环中i、j的范围是比k小?
因为已经约定*代码找的是以k为环中编号最大点的环的长度,按我的理解,其实这两层循环也可以写成
for(i=1;i<=m;i++){for(j=1;j<=n;j++){;}}
但是这样会重复计算很多环,大大降低了时间效率。

如果允许来回的路上经过重复点,并且没有必须经过两个不同点的限制,求指定的一个源点到任意点再回到源点的最短距离,可以怎么做?

答:可以用两次dij搞定,两次都是求出源点到任意点的最短路,只是第二次对应的图是原图的边方向反一下。
很显然,边反一下之后求出s到t的最短路其实是从t到s的最短路径。

#include<stdio.h>
#include<stdlib.h>
#define inf 10000000
#define maxn 110
int dist[maxn][maxn];
int map[maxn][maxn];
int main()
{
	int n,m;
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
				{
					map[i][j]=dist[i][j]=0;
				}
				else
				{
					map[i][j]=dist[i][j]=inf;
				}
		int a,b,c;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			if(c<dist[a][b])
			{
				map[a][b]=map[b][a]=dist[a][b]=dist[b][a]=c;
			}
		}
		int ans=inf;
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=k-1;i++)
				for(j=i+1;j<=k-1;j++)
					if(map[k][i]+dist[i][j]+map[j][k]<ans)
						ans=map[k][i]+dist[i][j]+map[j][k];
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		}

		
		if(ans>=inf)
			printf("It's impossible.\n");
		else
			printf("%d\n",ans);
	
	
	
	}

//system("pause");
return 0;
}

spfa模板

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 10000
#define maxe 100000
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn];
int pre[maxn];
int outque[maxn];
bool inque[maxn];
int n;
bool spfa(int s)
{
	int i;
	queue<int> q;
	memset(outque,0,sizeof(outque));
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	inque[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inque[u]=0;
		outque[u]++;
		if(outque[u]>n-1) return false;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				if(!inque[v])
				{
					q.push(v);
					inque[v]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
    memset(head,-1,sizeof(head));	



	system("pause");
	return 0;
}

堆优化的dij模板

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define maxe 10000000
#define inf 1000000000
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
bool visit[maxn];
int n;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int main()
{
    memset(head,-1,sieof(head)):

system("pause");
return 0;
}

Intelligent IME 暂存

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	struct Trie* next[27];
}Trie;
Trie* root=(Trie*)malloc(sizeof(Trie));
int 
void insert(char s[])
{
	int i,len=strlen(s);
	Trie *p=root,*q;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];
		}
		else
		{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=0;
			for(int j=1;j<=26;j++)
				q->next[j]=NULL;
			p->next[x]=q;
			p=q;
		}
	}
	p->v=1;
	return;
}
int find(char s[])
{
	int i,len=strlen(s);
	Trie* p=root;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];	
		}
		else
			return 0;
	}
	return p->v;//
}
void init()
{
	int i;
	for(i=1;i<=26;i++)
		root->next[i]=NULL;
	root->v=0;

	return;
}
void del(Trie*root)
{
	int i;
	for(i=1;i<=26;i++)
		if(root->next[i])
			del(root->next[i]);
	free(root);
	return;
}
void reset()
{
	int i;
	for(i=1;i<=26;i++)
		del(root->next[i]);
	return;	
}
void dfs(char num[],int cur,int len)
{
	int i;
	
	



}
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		init();
		int n,m;
		scanf("%d %d",&n,&m);
		getchar();
		char num[5010][10];
		char s[10];
		int cnt[5010];
		memset(cnt,0,sizeof(cnt));
		for(i=1;i<=n;i++)
		{
			gets(num[i]);
		}
		for(i=1;i<=m;i++)
		{
			gets(s);
			insert(s);
		}
		for(i=1;i<=n;i++)
		{
			int len=strlen(num[i]);
			dfs(num[i],0,len);
		}
	
	
		reset();
	}
	
	del(root);
system("pause");
return 0;
}

hdu 2294

求找错,找了一个晚上没发现错哪了。。

#include<string.h>
#include<stdlib.h>
#define maxn 40
#define mod 1234567891
typedef struct Mat{
	__int64 m[maxn*2][maxn*2];
}Mat;
Mat per;
int k;
void init()
{
	int i,j;
	for(i=0;i<=65;i++)
		for(j=0;j<=65;j++)
			per.m[i][j]=(i==j);
	return;
}
Mat multi(Mat a,Mat b)
{
	Mat ans;
	int i,j,t;
	for(i=0;i<=2*k+1;i++)
		for(j=0;j<=2*k+1;j++)
		{
			__int64 tmp=0;
			for(t=0;t<=2*k+1;t++)
				tmp+=a.m[i][t]*b.m[t][j];
			ans.m[i][j]=tmp%mod;
		}
	return ans;
}
Mat power(Mat a,int kk)
{
	Mat p=a,ans=per;
	while(kk)
	{
		if(kk&1)
		{
			kk--;
			ans=multi(ans,p);
		}
		else
		{
			kk/=2;
			p=multi(p,p);
		}
	}
	return ans;
}
Mat multi2(Mat a,Mat b)
{
	Mat ans;
	int i,j,t;
	for(i=0;i<=0;i++)
		for(j=0;j<=k;j++)
		{
			__int64 tmp=0;
			for(t=0;t<=k;t++)
				tmp+=a.m[i][t]*b.m[t][j];
			ans.m[i][j]=tmp%mod;
		
		}

	return ans;

}
int main()
{
	int i,j;
	init();
	Mat a;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d %d",&n,&k);
		memset(a.m,0,sizeof(a.m));
		for(i=0;i<=k;i++)
			for(j=0;j<=k;j++)
			{
				if(j-i==1)
					a.m[i][j]=k-i;
				else if(i==j)
					a.m[i][j]=i;
			}
		for(i=0;i<=k;i++)
			a.m[i][0]=0;
		for(i=0;i<=k;i++)
			for(j=k+1;j<=2*k+1;j++)
				a.m[i][j]=((j-i)==(k+1));
		for(i=k+1;i<=2*k+1;i++)
			for(j=k+1;j<=2*k+1;j++)
				a.m[i][j]=(i==j);

		Mat tmp=power(a,n+1);
		for(i=0;i<=k;i++)
			for(j=0;j<=k;j++)
				tmp.m[i][j]=tmp.m[i][j+k+1];
		Mat sr;
		for(i=0;i<=k;i++)
			sr.m[0][i]=0;
		sr.m[0][1]=1;
		Mat ans=multi2(sr,tmp);
		printf("%I64d\n",ans.m[0][k]);
	}
	system("pause");
	return 0;
}

关于树状数组成段更新、求单点值(转载)

这篇文章转载自http://hi.baidu.com/rere87/item/9959da0959933d12addc7093

这里面讲的一维树状数组成段更新,求单点值与前几天讲座上的思维方法不一样,而且讲的我彻底明白,而且加了二维树状数组成段更新,求单点值的方法(和一维树状数组的一样)

树状数组的优势就是在题目可以用它实现的时候程序又短常数又小

但是理解起来没有线段树那么直观

 

本文讲的主要是二维树状数组

二维树状数组就是对树状数组的扩展

将c[i]扩展到 c[i,j]

控制的是 a[(i-Lowbit[i]+1..i),(j-Lowbit[j]+1..j)]的元素和

每次更改和统计的时候用两个循环嵌套即可

具体可以看例题程序

 

例题:

 

题意:
    对于一个n*n(n <= 1000)的矩阵A,要求作如下操作:
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) 将当前范围内
的值和1异或。
2. Q x y (1 <= x, y <= n) 询问 A[x, y]。

解法:
    树状数组

思路:
    这题和树状数组的操作正好相反,树状数组是对点更新,成段求和,这题要
求成段更新,对点求值。但是还是可以转化,我们不妨先来考虑一维的情况,给
定一排数字,每次在区间进行进行成端加上一个数,然后询问某个点的值,很容
易想到线段树,但是线段树的常系数太大,我们试图用树状数组来解决,方法是
给定区间[a, b],如果要求在[a,b]区间都加上T我们只要在a的位置插入一个T,
然后在b+1的位置插入一个-T,这样下次询问某个值k的时候,只要将[1,k]的和求
出来就是k这个位置的值,为什么呢?分三种情况讨论:
1. k < a        先前的插入操作不影响此次结果   
2. a <= k <= b  a的位置插入T后,统计时值被加了一次
3. k > b。      a的位置有T,b+1的位置有-T,正好抵消
所以结论成立。
    然后就可以扩展到二维的情况,也是一样,如果对于(x1, y1) (x2, y2)这个
矩形,只要在(x1, y1) (x2+1, y2+1)这两个点插入T,而(x2+1, y1) (x1, y2+1)
这两个点插入-T即可。

树状数组

学习了树状数组,哈哈,有人教比自己理解快多了。。
单点更新,成段求和

//c数组初始化为0,刚开始的值其实就是add操作
#include<stdio.h>
#include<stdlib.h>
#define maxn 1000000
int c[maxn];
int n;//数组大小,同时也是树的根的下标
int lowbit(int x)
{
	return x & -x;
}
void add(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		c[i]+=x;
	return;
}
int getsum(int x)//1——x的和
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=c[i];
	return sum;
}
int main()
{

	return 0;
}

成段更新,求单点值
定义新数组d[] = a[i] – a[i-1]
特别的d[1] = a[1]
a[n] = d[1] + d[2] …+d[n]
a的[l,r]都加val d怎么变???
d[l] 加val d[r+1] 减val
and then??
跟前面一样,对d建立树状数组,唯一的不同,求和即是单点的值

成段更新,成段求和:

http://blog.csdn.net/q573290534/article/details/6664454

zoj3686(ZOJ Monthly, March 2013 A题)

终于A了前不久比赛的A题,当时完全木有想到线段树啊,主要是对树的先序遍历序列的性质陌生:在树的先序遍历序列中,一棵子树占据连续的一段序列。所以求出先序序列的同时记录每个节点代表的子树的起始index和最后index。然后就能在o i的时候更新线段树[sub[i].begin,sub[i].end]部分即可。
被异或运算和成段更新坑了好久。。

#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int> head[100000+10];
int ord[100000+10];
typedef struct Sub{
	int begin;
	int end;
}Sub;
Sub sub[100000+10];
int cnt=0;
typedef struct Tree{
	int l,r;
	int sum;
	int lazy;
}Tree;
Tree tree[4*100000+10];
void pushup(int rt)
{
	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
	return;
}
void pushdown(int rt)
{
	tree[rt<<1].lazy^=1;
	tree[rt<<1|1].lazy^=1;
	tree[rt<<1].sum=(tree[rt<<1].r-tree[rt<<1].l+1)-tree[rt<<1].sum;
	tree[rt<<1|1].sum=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)-tree[rt<<1|1].sum;
	tree[rt].lazy=0;
	return;
}
void build(int rt,int l,int r)
{
	tree[rt].l=l;
	tree[rt].r=r;
	tree[rt].lazy=0;
	if(l==r)
	{
		tree[rt].sum=0;
		return;
	}
	int m=(l+r)/2;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	pushup(rt);
	return;
}
void update(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		int len=tree[rt].r-tree[rt].l+1;
		tree[rt].sum=len-tree[rt].sum;
		tree[rt].lazy^=1;
		return;
	}
	if(tree[rt].lazy)
		pushdown(rt);
	int m=(tree[rt].l+tree[rt].r)/2;
	if(L<=m)
		update(rt<<1,L,R);
	if(R>m)
		update(rt<<1|1,L,R);
	pushup(rt);
	return;
}
int query(int rt,int L,int R)
{
	if(L<=tree[rt].l && tree[rt].r<=R)
	{
		return tree[rt].sum;
	}
	if(tree[rt].lazy)
		pushdown(rt);
	int m=(tree[rt].l+tree[rt].r)/2;
	int ans=0;
	if(L<=m)
		ans+=query(rt<<1,L,R);
	if(R>m)
		ans+=query(rt<<1|1,L,R);
	return ans;
}
void dfs(int cur)
{
	ord[++cnt]=cur;
	sub[cur].begin=cnt;
	int i;
	for(i=0;i<head[cur].size();i++)
	{
		int v=head[cur][i];
		dfs(v);
	}
	sub[cur].end=cnt;
	return;
}
int main()
{
	int n,m;
	int i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			if(!head[i].empty())
				head[i].clear();
		int fa;
		for(i=2;i<=n;i++)
		{
			scanf("%d",&fa);
			head[fa].push_back(i);
		}
		getchar();
		cnt=0;
		dfs(1);
		build(1,1,n);
		char c;
		int node;
		for(i=1;i<=m;i++)
		{
			scanf("%c %d",&c,&node);
			getchar();
			if(c=='o')
			{
				update(1,sub[node].begin,sub[node].end);

			
			}
			else
			{
				int ans=query(1,sub[node].begin,sub[node].end);
				printf("%d\n",ans);
			
			}
		}
		printf("\n");
	}
//system("pause");
return 0;
}


hdoj2196——两次树形dp(下->上、上->下)

开始想的太简单,以为到树中某点的距离最远的点只有两种情况:1.在以该点为根的子树的某个叶节点。2.从该点往上经过根结点,在从根结点到最远结点。
而事实上,看了网上的解题报告才发现,从某点往上的最远距离不一定经过根结点,但一定经过父节点。
dp[i].first表示以i点为根的子树中到点i的最远距离
dp[i].second表示以i点为根的子树中到点i的次远距离
dp[i].sonid表示对应于dp[i].first的i的那个儿子编号
(注意:上面的second指的是不和dp[i].first经过i的同一个儿子节点的最远距离)
dp2[i]表示经过i点的父亲的最远距离
这样两次dfs即可。第一次从下往上更新dp,第二次从上往下更新dp2(由于是从上往下更新,所以求解dp2[i->son]时用到的dp2[i]已经正确求解出来了,这样就保证了正确性)。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Edge{
	int to;
	int len;
	int next;
}Edge;
Edge edge[10010];
int head[10010],num[10010];
typedef struct DP{
	int first;
	int second;
	int sonid;
}DP;
DP dp[10010];
int dp2[10010];
int max(int a,int b)
{
	return a>b?a:b;
}
void dfs(int cur)
{
	int i,d=num[cur];
	if(d==0)
	{
		return;
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		dfs(son);
		if(dp[son].first+edge[i].len>dp[cur].first)
		{
			dp[cur].first=dp[son].first+edge[i].len;
			dp[cur].sonid=son;
		}
		
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		if(son!=dp[cur].sonid)
		{
			if(dp[son].first+edge[i].len>dp[cur].second)
				dp[cur].second=dp[son].first+edge[i].len;
		}
	
	}
	return;
}
void dfs2(int cur,int fa,int len)
{
	int i;
	if(fa!=-1)
	{
		if(cur!=dp[fa].sonid)
		{
			dp2[cur]=max(dp[fa].first,dp2[fa])+len;
		
		}
		else
		{
			dp2[cur]=max(dp[fa].second,dp2[fa])+len;
		}
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int son=edge[i].to;
		dfs2(son,cur,edge[i].len);
		
	}
	return;
}
int main()
{
	int n;
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			continue;
		if(n==1)
		{
			printf("0\n");
			continue;
		}
		memset(head,-1,sizeof(head));
		memset(num,0,sizeof(num));
		memset(dp2,0,sizeof(dp2));
		for(i=1;i<=n;i++)
		{
			dp[i].first=0;
			dp[i].second=0;
			dp[i].sonid=0;
		}
		int cnt=0;
		for(i=2;i<=n;i++)
		{
			int fa,len;
			scanf("%d %d",&fa,&len);
			edge[cnt].len=len;
			edge[cnt].to=i;
			edge[cnt].next=head[fa];
			head[fa]=cnt++;
			num[fa]++;
		}
		dfs(1);
		dfs2(1,-1,0);
		for(i=1;i<=n;i++)
		{
			printf("%d\n",max(dp[i].first,dp2[i]));
		}
			


	}
//system("pause");
return 0;
}