UVA 11090 - Going in Cycle!! SPFA

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2031

题目大意：

给定一个n个点m条边的加权有向图，求平均权值最小的回路。

思路：

用二分法求解。假设答案为mid，只需要判断是否存在平均值小于Mid的回路。怎么判断呢？假设一个包含k条边的回路，回路上各条边的权值为w1,w2……wk，那么平均值小于mid意味着 w1+w2+……wk< k* mid即：

（w1-mid)+(w2-mid)+……(wk-mid)<0

换句话说，只要把图中没一条边a,b的权值w(a,b)变为w(a,b)-mid，在判断图中有没有负权回路。

怎么判断负权回路呢？这就是SPFA的用法了，一个顶点入队列超过n次，就表示有回路。

记住这个不一定是联通的图。所以一开始要把所有的点加入队列。WA找了半天看了别人代码才发现。

---------------2014/01/26----------

想起可以增加一个点0，从该点到所有点的权值为0，那么可以保证改图连通，并且不会破坏负环~~~~~~

代码如下：

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=52;

const int INF=100000000;

struct edge

{

	int to;

	double val;

	int next;

}e[MAXN*MAXN];

int head[MAXN],len,n,m;

void add(int from,int to,double val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

bool spfa()

{

	double dis[MAXN];

	bool vis[MAXN]={0};

	int cnt[MAXN]={0};

	queue<int> q;

	for(int i=1;i<=n;i++)       //图可能是非联通的，所以一开始要把全部加入。WA在这里

		dis[i]=INF;

	q.push(0);

	vis[0]=cnt[0]=1;

	dis[0]=0;

	while(!q.empty())

	{

		int cur=q.front();

		q.pop();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[cur] + e[i].val < dis[id])

			{

				dis[id]=dis[cur]+e[i].val;

				if(!vis[id])

				{

					cnt[id]++;

					vis[id]=true;

					q.push(id);

					if(cnt[cur] > n)

						return true;

				}

			}

		}

	}

	return false;

}

void change(double  x)

{

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

		for(int i=head[k];i!=-1;i=e[i].next)

			e[i].val+=x;

}

bool test(double x)

{

	change(-x);

	bool ok=spfa();

	change(x);

	return ok;

}

int main()

{

	int T;

	scanf("%d",&T);

	for(int ri=1;ri<=T;ri++)

	{

		len=0;

		memset(head,-1,sizeof(head));

		double L=INF,R=0;

		scanf("%d%d",&n,&m);

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

		{

			int from,to;

			double val;

			scanf("%d%d%lf",&from,&to,&val);

			if(R< val)

				R=val;

			if(L > val)

				L=val;

			add(from,to,val);

		}

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

			add(0,i,0);

		printf("Case #%d: ",ri);

		if(!test(R+1))

		{

			printf("No cycle found.\n");

			continue;

		}

		while(R-L > 1e-3)             //浮点数判断大小要这样

		{

			double mid = L + (R-L)/2;

			if(test(mid))

				R = mid;

			else

				L = mid;

		}

		printf("%.2lf\n",R);

	}

	return 0;

}

一开始全部加入队列版本

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=52;

const int INF=100000000;

struct edge

{

	int to;

	double val;

	int next;

}e[MAXN*MAXN];

int head[MAXN],len,n,m;

void add(int from,int to,double val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

bool spfa()

{

	double dis[MAXN];

	bool vis[MAXN];

	int cnt[MAXN];

	queue<int> q;

	for(int i=1;i<=n;i++)       //图可能是非联通的，所以一开始要把全部加入。WA在这里

	{

		dis[i]=INF;

		vis[i]=true;

		cnt[i]=1;

		q.push(i);

	}

	while(!q.empty())

	{

		int cur=q.front();

		q.pop();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[cur] + e[i].val < dis[id])

			{

				dis[id]=dis[cur]+e[i].val;

				if(!vis[id])

				{

					cnt[id]++;

					vis[id]=true;

					q.push(id);

					if(cnt[cur] > n)

						return true;

				}

			}

		}

	}

	return false;

}

void change(double  x)

{

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

		for(int i=head[k];i!=-1;i=e[i].next)

			e[i].val+=x;

}

bool test(double x)

{

	change(-x);

	bool ok=spfa();

	change(x);

	return ok;

}

int main()

{

	int T;

	scanf("%d",&T);

	for(int ri=1;ri<=T;ri++)

	{

		len=0;

		memset(head,-1,sizeof(head));

		double L=INF,R=0;

		scanf("%d%d",&n,&m);

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

		{

			int from,to;

			double val;

			scanf("%d%d%lf",&from,&to,&val);

			if(R< val)

				R=val;

			if(L > val)

				L=val;

			add(from,to,val);

		}

		printf("Case #%d: ",ri);

		if(!test(R+1))

		{

			printf("No cycle found.\n");

			continue;

		}

		while(R-L > 1e-3)             //浮点数判断大小要这样

		{

			double mid = L + (R-L)/2;

			if(test(mid))

				R = mid;

			else

				L = mid;

		}

		printf("%.2lf\n",R);

	}

	return 0;

}

巴特西

UVA 11090 - Going in Cycle!! SPFA

最新文章

热门文章