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

图论500题

=============================以下是最小生成树+并查集======================================
【HDU】
1213 How Many Tables 基础并查集★
1272 小希的迷宫 基础并查集★
1325&&poj1308 Is It A Tree? 基础并查集★
1856 More is better 基础并查集★
1102 Constructing Roads 基础最小生成树★
1232 畅通工程 基础并查集★
1233 还是畅通工程 基础最小生成树★
1863 畅通工程 基础最小生成树★
1875 畅通工程再续 基础最小生成树★
1879 继续畅通工程 基础最小生成树★
3371 Connect the Cities 简单最小生成树★
1301 Jungle Roads 基础最小生成树★
1162 Eddy’s picture 基础最小生成树★
1198 Farm Irrigation 基础最小生成树★
1598 find the most comfortable road 枚举+最小生成树★★
1811 Rank of Tetris 并查集+拓扑排序★★
3926 Hand in Hand 同构图★
3938 Portal 离线+并查集★★
2489 Minimal Ratio Tree dfs枚举组合情况+最小生成树★
4081 Qin Shi Huang’s National Road System 最小生成树+DFS★★
4126 Genghis Khan the Conqueror 枚举+最小生成树+DFS(难)★★★★

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

1020

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 1000000000
int dest[15];
int dist[100000][100000];
int ans,s;
bool visit[15];
void dfs(int pre,int cur,int len,int cnt)
{
	int i;
	if(cur!=0)
		visit[cur]=1;
	len+=dist[pre][cur];
	if(cnt==s)
	{
		len+=dist[cur][0];
		if(len<ans)
			ans=len;
		return;
	}
	for(i=1;i<=s;i++)
	{
		if(!visit[dest[i]])
		{
			dfs(cur,dest[i],len,cnt+1);
			visit[dest[i]]=0;
		}
	
	}
	return;
}
int main()
{
    int t;
	int i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;

		scanf("%d %d",&n,&m);
		for(i=0;i<=n-1;i++)
			for(j=0;j<=n-1;j++)
				if(i==j)
					dist[i][j]=0;
				else
					dist[i][j]=inf;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&w);
			if(w<dist[a][b])
			{
				dist[a][b]=dist[b][a]=w;
			}
		}
		scanf("%d",&s);
		for(i=1;i<=s;i++)
		{
			scanf("%d",&dest[i]);
		}
		for(k=0;k<=n-1;k++)
			for(i=0;i<=n-1;i++)
				for(j=0;j<=n-1;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		memset(visit,0,sizeof(visit));
		ans=inf;
		dfs(0,0,0,0);
		printf("%d\n",ans);
	
	
	
	
	
	}

system("pause");
return 0;
}