弗洛伊德Floyd求最小环

模板:

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;
const int INF = 0xffffff0;
int temp,Map[MAXN][MAXN],Dist[MAXN][MAXN],pre[MAXN][MAXN],ans[MAXN*]; void Solve(int i,int j,int k)
{
temp = ; //回溯,存储最小环
while(i != j)
{
ans[temp++] = j;
j = pre[i][j];
}
ans[temp++] = i;
ans[temp++] = k;
}
void Floyd(int N)
{
for(int i = ; i <= N; ++i)
for(int j = ; j <= N; ++j)
{
Dist[i][j] = Map[i][j];
pre[i][j] = i;
}
int MinCircle = INF; //最小环
for(int k = ; k <= N; ++k)
{
for(int i = ; i <= N; ++i)
{
for(int j = ; j <= N; ++j)
{
if(i != j && Dist[i][j] != INF && Map[i][k] != INF && Map[k][j] != INF
&& Dist[i][j] + Map[i][k] + Map[k][j] < MinCircle)
{
MinCircle = min(MinCircle, Dist[i][j] + Map[i][k] + Map[k][j]);
Solve(i,j,k); //回溯存储最小环
}
}
} for(int i = ; i <= N; ++i)
{
for(int j = ; j <= N; ++j)
{
if(Dist[i][k] != INF && Dist[k][j] != INF &&
Dist[i][k] + Dist[k][j] < Dist[i][j])
{
Dist[i][j] = Dist[i][k] + Dist[k][j];
pre[i][j] = pre[k][j]; //记录点i到点j的路径上,j前边的点
}
}
}
} if(MinCircle == INF) //不存在环
{
printf("No solution.\n");
return;
}
//如果求出最小环为负的,原图必定存在负环
for(int i = ;i < temp; ++i) //输出最小环
if(i != temp-)
printf("%d ",ans[i]);
else
printf("%d\n",ans[i]);
}

例题:

BZOJ1027: [JSOI2007]合金

思路:给定两个点集A和B,求A中最小的一个子集S,使B中所有的点在S的凸包内部。枚举A点集两点i,j(i可以等于j)若B点集中的所有点都在向量i->j的左侧或线段ij上,就连接一条i->j的单向边,然后Floyd求最小环即可。

#include<bits/stdc++.h>

#define eps 1e-8
using namespace std;
struct node
{
double x,y,z;
}a[],b[];
double multi(node p1,node p2,node p0)
{
double x1=p1.x-p0.x;
double y1=p1.y-p0.y;
double x2=p2.x-p0.x;
double y2=p2.y-p0.y;
return x1*y2-x2*y1;
}
double dis(node p1,node p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int d[][];
int main()
{
int n,m;
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);
for(int i=;i<=n;i++) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[i].z);
int i,j,k;double t;
memset(d,0x3f,sizeof(d));
for(i=;i<=m;i++)
for(j=;j<=m;j++)
{
for(k=;k<=n;k++)
{
t=multi(a[j],b[k],a[i]);
if(t<-eps) break;
if( fabs(t)<eps && dis(a[i],b[k])>dis(a[i],a[j]) )break;
}
if(k==n+) d[i][j]=;
}
for(k=;k<=m;k++)
for(i=;i<=m;i++)if(i!=k)
for(j=;j<=m;j++)if(j!=k)
if( d[i][j]>d[i][k]+d[k][j] )d[i][j]=d[i][k]+d[k][j];
int ans=m+;
for(i=;i<=m;i++) if(ans>d[i][i])ans=d[i][i];
if(ans==m+)printf("-1\n");else printf("%d\n",ans); return ;
}
上一篇:【BZOJ 1027】 (凸包+floyd求最小环)


下一篇:CF 1206D - Shortest Cycle Floyd求最小环