P2868 [USACO07DEC]观光奶牛Sightseeing Cows

---


---

错误日志： dfs 判负环没有把初值赋为 \(0\) 而是 \(INF\)， 速度变慢

---

Solution

设现在走到了一个环， 环内有 \(n\) 个点， \(n\) 条边， 点权为 \(f_{i}\)， 边权为 \(e_{i}\)

设 \(k = \sum_{i = 1}^{n}\frac{f_{i}}{e_{i}}\)， 显然是 0/1分数规划模型， 变形可得： \(\sum_{i = 1}^{n}f_{i} - k * ei \geq 0\) 时 \(k\) 合法

此式不太好判断， 我们在不等式两边乘上 \(-1\)， 得 \(\sum_{i = 1}^{n}k * e_{i} - f_{i} \leq 0\) ，转换为图中负环的判定

若存在负环则此 \(k\) 合法

二分求解0/1分数规划即可

求负环的时候， 初始距离全部设为 \(0\)

如果有负环的话此个距离 \(0\) 肯定能变得更小， 赋0可以减少更新量， 加快效率

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 2019,INF = 1e9, maxv = 20019;;

int head[maxn],nume = 1;

struct Node{

    int v,dis,nxt;

    }E[maxv << 3];

void add(int u,int v,int dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

int num, nr;

double f[maxn];//愉♂悦值

double d[maxn];

bool ins[maxn], vis[maxn], flag;

void SPFA_dfs(int u, double k){

	ins[u] = 1, vis[u] = 1;

	for(int i = head[u];i;i = E[i].nxt){

		int v = E[i].v;

		double dis = E[i].dis;

		if(d[u] + k * dis - f[v] <= d[v]){

			if(ins[v] || flag){flag = 1;return ;}

			d[v] = d[u] + k * dis - f[v];

			SPFA_dfs(v, k);

			}

		}

	ins[u] = 0;

	}

bool check(double k){

	REP(i, 1, num)d[i] = 0, vis[i] = 0, ins[i] = 0;

	flag = 0;

	REP(i, 1, num){

		if(!vis[i])d[i] = 0, SPFA_dfs(i, k);

		if(flag)return 1;

		}

	return flag;

	}

double search(double l, double r){

	double ans;

	while(r - l >= 1e-3){

		double mid = (l + r) / 2;

		if(check(mid))ans = mid, l = mid;

		else r = mid;

		}

	return ans;

	}

double maxx = 0;

int main(){

	num = RD(), nr = RD();

	REP(i, 1, num)f[i] = RD(), maxx += f[i];

	REP(i, 1, nr){

		int u = RD(), v = RD(), dis = RD();

		add(u, v, dis);

		}

	printf("%.2lf\n", search(0, maxx));

	return 0;

	}