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转移。(普通的链式前向星中是无法知道一个点的前驱的)

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

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

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

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

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;
}

zoj3686(ZOJ Monthly, March 2013 A题)

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

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]已经正确求解出来了,这样就保证了正确性)。