程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3621 Sightseeing Cows(最優比例生成環，01分數規劃)

poj 3621 Sightseeing Cows(最優比例生成環，01分數規劃)

編輯：C++入門知識

http://poj.org/problem?id=3621

大致題意：給出一個有向圖，每個點都有一個點權，每條有向邊也都有一個邊權，要求出一個環使得環中點權之和與邊權之和的比值最大。

思路：和最優比率生成樹異曲同工。設點權是v[i],邊權是e[i]。不同的是這裡一個是點，一個是邊。怎麼像生成樹一樣把這兩個值放到一起呢？可以把他們都轉化到邊上。同樣的二分λ，每次給邊重新賦權為v[i] - λ*e[i](v[i]是該邊終點的點權)。因為要求比值最大，那麼在這前提下於圖中的所有環都<=0, 所以我們只需每次spfa判斷是否有正環，若有說明λ偏小，否則λ偏大。其實每條邊的權值取上述(v[i] - λ*e[i])的負值，然後spfa判負環也可以，試了下，時間上差不多。下面的代碼判的是負環。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-7
using namespace std;
const _LL INF = 1e18;
const int maxn = 1010;

struct node
{
	int v;
	double w;
};
vector  edge[maxn];

int Map[maxn][maxn];
int fun[maxn];
int n,m;

bool spfa(double mid)
{
	queue  que;
	while(!que.empty()) que.pop();
	int inque[maxn],in[maxn];
	double dis[maxn];

	memset(inque,0,sizeof(inque));
	memset(in,0,sizeof(in));
	for(int i = 1; i <= n; i++)
	{
		que.push(i);
		dis[i] = 0;
		in[i] = 1;
		inque[i] = 1;
	}

	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = 0;

		for(int i = 0; i < (int)edge[u].size(); i++)
		{
			int v = edge[u][i].v;
			double w = edge[u][i].w * mid - fun[v];
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!inque[v])
				{
					inque[v] = 1;
					que.push(v);
					in[v]++;
					if(in[v] > n)
						return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		int u,v,w;
		for(int i = 1; i <= n; i++)
			edge[i].clear();
		for(int i = 1; i <= n; i++)
			scanf("%d",&fun[i]);
		for(int i = 1; i <= m; i++)
		{
			scanf("%d %d %d",&u,&v,&w);
			Map[u][v] = w;
			edge[u].push_back((struct node){v,w});
		}

		double l = 0.0, r = 1000.0;
		double mid;
		while(fabs(r-l) > eps)
		{
			mid = (l+r)/2;
			if(spfa(mid))
				l = mid;
			else r = mid;
		}
		printf("%.2f\n",l);
	}
	return 0;
}