[USACO4.1]篱笆回路Fence Loops

题目：USACO Training 4.1（在官网上提交需加文件输入输出）、洛谷P2738。

题目大意：给你一张图里的边集，让你求出这张图的最小环。

解题思路：求最小环很简单，用Floyd即可。最重要的是，该题给你的是边集而不是点集，所以构图是关键。

我是这么构图的：设当前边的编号为$x$，我们先把它左端点编号设为$2x-1$，右端点编号设为$2x$，然后用$dy[p]$表示编号为$p$的点实际是第几个点（意思大致是，先假设每条边是独立的，然后把端点进行合并。例如2号边和3号边的左端点相连，则dy[2*2-1]=dy[3*2-1]=(合并后的那个点的编号)）。具体见代码实现。

我写好建图的代码后又被一个东西坑了：样例里边读入时是排好序的，于是我认为数据里也是这些，然后就WA了TAT……所以得先把边按编号排序，然后建图。

C++ Code：

#include<cstdio>

#include<algorithm>

#include<cstring>

#define ls(i) (i*2-1)

#define rs(i) (i*2)

using namespace std;

int n,m=0,dis[320][320],p[320][320],dy[240];

struct Edge{

	int s,l,lk,rk;

	int a[2][120];

	bool b[2][120];

	bool operator <(const Edge& rhs)const{return s<rhs.s;}

}e[120];

void init(){//读入

	scanf("%d",&n);

	memset(e,0,sizeof(e));

	for(int i=1;i<=n;++i){

		scanf("%d%d%d%d",&e[i].s,&e[i].l,&e[i].lk,&e[i].rk);

		for(int j=1;j<=e[i].lk;++j){

			int x;

			scanf("%d",&x);

			e[i].a[0][j]=x;

			e[i].b[0][x]=true;

		}

		for(int j=1;j<=e[i].rk;++j){

			int x;

			scanf("%d",&x);

			e[i].a[1][j]=x;

			e[i].b[1][x]=true;

		}

	}

	sort(e+1,e+n+1);

}

void build_graph(){//建图

	memset(dy,-1,sizeof dy);

	memset(p,0x1f,sizeof p);

	for(int i=1;i<=n;++i){

		for(int j=1;j<=e[i].lk;++j){

			int v=e[i].a[0][j];

			if(e[v].b[0][i]&&dy[ls(v)!=-1])dy[ls(i)]=dy[ls(v)];else

			if(e[v].b[1][i]&&dy[rs(v)!=-1])dy[ls(i)]=dy[rs(v)];

			if(dy[ls(i)]!=-1)break;

		}

		if(dy[ls(i)]==-1)dy[ls(i)]=++m;

		for(int j=1;j<=e[i].rk;++j){

			int v=e[i].a[1][j];

			if(e[v].b[0][i]&&dy[ls(v)]!=-1)dy[rs(i)]=dy[ls(v)];else

			if(e[v].b[1][i]&&dy[rs(v)]!=-1)dy[rs(i)]=dy[rs(v)];

			if(dy[rs(i)]!=-1)break;

		}

		if(dy[rs(i)]==-1)dy[rs(i)]=++m;

		p[dy[ls(i)]][dy[rs(i)]]=p[dy[rs(i)]][dy[ls(i)]]=e[i].l;

	}

}

int floyd(){//Floyd求最小环

	int Min=0x1f1f1f1f;

	memcpy(dis,p,sizeof dis);

	for(int k=1;k<=m;++k){

		for(int i=1;i<k;++i)

		for(int j=i+1;j<k;++j)

		Min=min(Min,dis[i][j]+p[i][k]+p[k][j]);

		for(int i=1;i<=m;++i)

		if(i!=k)

		for(int j=1;j<=m;++j)

		if(i!=j&&j!=k)

		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	}

	return Min;

}

int main(){

	init();

	build_graph();

	printf("%d\n",floyd());

	return 0;

}

巴特西

[USACO4.1]篱笆回路Fence Loops

最新文章

热门文章