差分约束专题

希望读者把思路和代码先当成空气,不到万不得已不要看思路,代码最好不要看,可以用来对拍。
首先,对于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;
}

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论文全集>点我下载