hdoj部分最短路题

hdoj1245
简单题,spfa二维最短路,也可以用dij来做,注意:如果用spfa来做,那么开始建图的时候,对于距离>d的两个点不要连边,如果这里连了而在松弛的时候判断w与d的关系会超时。
这里其他点到起点不用连边,因为显然不会回到源点(如果中途回到原点再到其他点何不开始时就直接到那个点呢,对吧),因为图中边权均为正的,所以不用判环,算法一定可以结束。

差分约束专题

希望读者把思路和代码先当成空气,不到万不得已不要看思路,代码最好不要看,可以用来对拍。
首先,对于a-b>=w建模:b->(w)->a
一句经典的话:最短路求出的是最大解,最长路求出的是最小解。
因为求最短路时dist赋的初值是inf,它在松弛变小过程中,一旦满足约束条件就退出,所以是最大值,最长路的情况也是一个道理。(注意,这里的最大值最小值是相对inf和-inf而言的,数学上,差分约束的解是没有最大值和最小值的)
关于求dist[1]和dist[n]之间差最大。
其实我认为求最短路和求最长路都能解决这个问题,对于最短路,新建超级源点,向每个点连边,权0。这相当于增加约束条件dist[i]<=0,因为dist[i]初始化为inf,所以不断松弛直到dist[i]<=0,这是求出的是差距最小的。求最长路的过程也可以这样分析。

HDU 4360

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#define maxn 10000
#define maxe 200010
#define inf 1000000000
using namespace std;
typedef struct Edge{
	int w;
	int id;
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dist[maxn][4];
bool inque[maxn][4];
int num[maxn][4];
int n,m;
typedef struct node{
	int u;
	int id;
}node;
bool spfa(int s)
{
	int i,j;
	queue<node> q;
	memset(inque,0,sizeof(inque));
	for(i=1;i<=n;i++)
		for(j=0;j<=3;j++)
		{
			dist[i][j]=inf;
			num[i][j]=0;
		}
	dist[s][3]=0;
	num[s][3]=0;
	node sr;
	sr.u=s;sr.id=3;
	q.push(sr);
	inque[s][3]=1;
	while(!q.empty())
	{
		int u=q.front().u;id=q.front().id;
		q.pop();
		inque[u][id]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			int x=edge[i].id;
			if(dist[u][id]+edge[i].w<dist[v][x] && (id+1)%4==x)
			{
				dist[v][x]=dist[u][id]+edge[i].w;
				num[v][x]=num[u][id];
				if(x==3)
					num[v][x]++;
			}
			else if(dist[u][id]+edge[i].w==dist[v][x] && (id+1)%4==x && num[v][x]<=num[u][id])
			{
				num[v][x]=num[u][id];
				if(x==3)
					num[v][x]++;
			
			}
			
		}
	}
	return true;
}
int index[200];
int main()
{
    int i,j;
	int t;
	index['L']=0;
	index['O']=1;
	index['V']=2;
	index['E']=3;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		int cnt=0;
		scanf("%d %d",&n,&m);
		char c;
		int u,v;
		__int64 w;
		for(i=1;i<=n;i++)
		{
			scanf("%d %d %I64d %c",&u,&v,&w,&c);
			getchar();
			edge[cnt].id=love[c];
			edge[cnt].w=w;
			edge[cnt].to=v;
			edge[cnt].next=head[u];
			head[u]=cnt++;

			edge[cnt].id=love[c];
			edge[cnt].w=w;
			edge[cnt].to=u;
			edge[cnt].next=head[v];
			head[v]=cnt++;

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

1003

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#define maxn 10010
#define maxe 20010
#define inf 1000000000
using namespace std;
typedef struct node{
	int point;
	double dist;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	double w;
	int from;
	int to;
	int next;
}Edge;
int head1[maxn],head2[maxn];
Edge edge1[maxe],edge2[maxe];
double dist1[maxn],dist2[maxn];
int pre[maxn];
bool visit[maxn];
int n,m;
typedef struct Point{
	int x,y,z;
}Point;
Point point[maxn];
int level[maxe];
void dij(int s,double* dist,Edge edge[],int head[])
{
	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;
}
double cal_dist(int u,int v)
{
	int x1=point[u].x,x2=point[v].x;
	int y1=point[u].y,y2=point[v].y;
	int z1=point[u].z,z2=point[v].z;
	double x=double(x1-x2);
	double y=double(y1-y2);
	double z=double(z1-z2);
	return sqrt(x*x+y*y+z*z);
}
double cal_planedist(int u,int v)
{
	int x1=point[u].x,y1=point[u].y;
	int x2=point[v].x,y2=point[v].y;
	double x=double(x1-x2);
	double y=double(y1-y2);
	return sqrt(x*x+y*y);

}
typedef struct Keyedge{
	int index;
	int u;
	int v;
}Keyedge;
Keyedge key[maxe];
int main()
{
    int i,j;
	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0)
	{
		int cnt1=0,cnt2=0;
		memset(head1,-1,sizeof(head1));
		memset(head2,-1,sizeof(head2));
		for(i=1;i<=n;i++)
		{
			scanf("%d %d %d",&point[i].x,&point[i].y,&point[i].z);
		}
		for(i=1;i<=m;i++)
		{
			int u,v;
			int index=2*(i-1);
			scanf("%d %d",&u,&v);
			double w=cal_dist(u,v);
			edge1[cnt1].w=w;
			edge1[cnt1].from=u;
			edge1[cnt1].to=v;
			edge1[cnt1].next=head1[u];
			head1[u]=cnt1++;

			edge1[cnt1].w=w;
			edge1[cnt1].from=v;
			edge1[cnt1].to=u;
			edge1[cnt1].next=head1[v];
			head1[v]=cnt1++;

			if(point[u].z>point[v].z)
			{
				level[index]=0;
				level[index+1]=(int)(100*(point[u].z-point[v].z)/cal_planedist(u,v));
			}
			else if(point[u].z<point[v].z)
			{
				level[index+1]=0;
				level[index]=(int)(100*(point[v].z-point[u].z)/cal_planedist(u,v));				

			}
			else
			{
				level[index]=level[index+1]=0;	
			}

			edge2[cnt2].w=w;
			edge2[cnt2].from=v;
			edge2[cnt2].to=u;
			edge2[cnt2].next=head2[v];
			head2[v]=cnt2++;

			edge2[cnt2].w=w;
			edge2[cnt2].from=u;
			edge2[cnt2].to=v;
			edge2[cnt2].next=head2[u];
			head2[u]=cnt2++;
		
		}
		int s,t,d;
		scanf("%d %d %d",&s,&t,&d);
		int cur=0;
		for(i=0;i<=cnt1-1;i++)
			if(level[i]==d)
			{
				key[++cur].index=i;
				key[cur].u=edge1[i].from;
				key[cur].v=edge1[i].to;

			}
			if(level[i]>d)
			{
				edge1[i].w=inf;
			}
		if(cur==0)
		{
			printf("None\n");
			continue;
		}
		dij(s,dist1,edge1,head1);
		cur=0;
		for(i=0;i<=cnt2-1;i++)
			if(level[i]>d)
			{
				edge2[i].w=inf;
			}

		dij(t,dist2,edge2,head2);
		double ans=inf;
		for(i=1;i<=cur;i++)
		{
			int u=key[i].u;
			int v=key[i].v;
			j=key[i].index;
			double tmp=dist1[u]+edge1[j].w+dist2[v];
			if(tmp<ans)
				ans=tmp;
		}
		printf("%.1lf\n",ans);



	
	
		scanf("%d %d",&n,&m);
	}

system("pause");
return 0;
}

hdoj2433

这题真的写的痛苦流涕,看代码长度就知道了,比赛时候遇到目测没几十分钟绝对无法写出来(想不想的到还是个问题。。)
不知道是不是oj的问题,同样的代码WA好几次,最后一次却过了。。
8184304 2013-04-27 13:14:48 Accepted 2433 1703MS 844K 2714 B C++ shadow
8183928 2013-04-27 11:23:12 Wrong Answer 2433 890MS 408K 2727 B C++ shadow
8183893 2013-04-27 11:17:05 Wrong Answer 2433 828MS 384K 2726 B G++ shadow
8183858 2013-04-27 11:10:06 Compilation Error 2433 0MS 0K 546 B C++ shadow
8183855 2013-04-27 11:09:51 Wrong Answer 2433 890MS 408K 2726 B C++ shadow
8182801 2013-04-26 23:53:22 Wrong Answer 2433 921MS 408K 2694 B C++ shadow
8182797 2013-04-26 23:52:49 Wrong Answer 2433 906MS 408K 2693 B C++ shadow
8182790 2013-04-26 23:51:54 Wrong Answer 2433 890MS 408K 2693 B C++ shadow
8181185 2013-04-26 21:12:40 Wrong Answer 2433 781MS 408K 2645 B C++ shadow
8181053 2013-04-26 21:01:47 Time Limit Exceeded 2433 2000MS 632K 2600 B C++ shadow
8181042 2013-04-26 21:00:55 Runtime Error
(ACCESS_VIOLATION) 2433 0MS 320K 2603 B C++ shadow

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一样,距离源点最短距离小的点会先被定标。所以一个点的最短路肯定比次短路先永久确定(显然,一个点的最短路肯定短于次短路)。

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