CF1204C Anna, Svyatoslav and Maps

题意简述

　　题目链接

　　给定一张n个点的有向图，一个长度为m的点号序列，表示图中一条路径（不保证是简单路径），要求选出其一个子序列，使得原序列是依次经过该子序列中所有点的一条最短路径，最小化子序列长度并输出该子序列。

算法概述

　　把原序列变成子序列，要使子序列长度最小化，则对于原序列中的点，当然是能删就删。

　　动手画一画三个样例，不难发现一个结论：对于原序列中连续的三个点p,v,q，若dis[p,q]=dis[p,v]+dis[v,q]，则v点可以删去。其中dis[i,j]表示点i,j之间的最短路径。

　　结论的正确性不难证明，由于满足上述等式，则p->v->q是p,q之间的一条最短路径，则可以将v删去，充分性成立。

　　若可以将v删去，则说明p->v->q是p,q之间的一条最短路径，那么必然满足dis[p,q]=dis[p,v]+dis[v,q]，必要性成立。

　　故结论成立。

　　有了上述结论，我们就可以直接用Floyd算法预处理出任意两点间的最短路径，然后依次遍历原序列中每个点，判断若该点是否可以删去，能删则删。由于删点之后还可能要用到该点的前驱节点，普通队列无法处理，故我们可以用链表处理这个序列。

　　时间复杂度O(n³+m)。

参考代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=110,M=1e6+10;
struct Node{
	int pre,nex,dat;
	#define pre(p) pot[p].pre
	#define nex(p) pot[p].nex
	#define dat(p) pot[p].dat
}pot[M];

void remove(int p)
{
	pre(nex(p))=pre(p);
	nex(pre(p))=nex(p);
	pre(p)=nex(p)=-1;
}

void insert(int x,int p,int val)
{
	pre(p)=x;
	nex(p)=-1;
	nex(x)=p;
	dat(p)=val;
}

int g[N][N];
int dis[N][N];
int n,m;

void floyd()
{
	memset(dis,0x3f,sizeof dis);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(i==j)dis[i][j]=0;
			else if(g[i][j]==1)dis[i][j]=1;
		}
	
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(dis[i][j]>dis[i][k]+dis[k][j])
					dis[i][j]=dis[i][k]+dis[k][j];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%1d",&g[i][j]);
	
	floyd();
	
	scanf("%d",&m);
	pre(0)=-1;
	for(int i=1;i<=m;i++)
	{
		int p;scanf("%d",&p);
		insert(i-1,i,p);
	}
	
	int cnt=m;
	for(int i=2;i<=m-1;i++)
	{
		int last=dat(pre(i)),next=dat(nex(i));
		int now=dat(i);
		if(dis[last][next]==dis[last][now]+dis[now][next])remove(i),cnt--;
	}
	
	printf("%d
",cnt);
	for(int i=nex(0);~i;i=nex(i))
		printf("%d ",dat(i));
	
	return 0;
}