0/1分数规划,二分求索答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = 5050;
int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];
void add(int a, int b, int c) {
e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool check(double mid) {
memset(dist, 0, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ ) {
q[tt ++ ] = i;
st[i] = true;
}
while (hh != tt) {
int x = q[hh ++ ];
if (hh == N) hh = 0;
st[x] = false;
for (int i = h[x]; ~i; i = ne[i]) {
int y = e[i];
double z = wf[x] - mid * wt[i];
if (dist[y] < dist[x] + z) {
dist[y] = dist[x] + z;
cnt[y] = cnt[x] + 1;
if (cnt[y] >= n) return true;
if (!st[y]) {
st[y] = true;
q[tt ++ ] = y;
if (tt == N) tt = 0;
}
}
}
}
return false;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> wf[i];
for (int i = 0; i < m; i ++ ) {
int x, y, z; cin >> x >> y >> z;
add(x, y, z);
}
double l = 0, r = 1e6;
while (r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", l);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = 5050;
int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];
void add(int a, int b, int c) {
e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool check(double mid) {
memset(dist, 0, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
queue<int> q;
for (int i = 1; i <= n; i ++ ) {
q.push(i);
st[i] = true;
}
while (q.size()) {
int x = q.front(); q.pop();
st[x] = false;
for (int i = h[x]; ~i; i = ne[i]) {
int y = e[i];
double z = wf[x] - mid * wt[i];
if (dist[y] < dist[x] + z) {
dist[y] = dist[x] + z;
cnt[y] = cnt[x] + 1;
if (cnt[y] >= n) return true;
if (!st[y]) {
st[y] = true;
q.push(y);
}
}
}
}
return false;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> wf[i];
for (int i = 0; i < m; i ++ ) {
int x, y, z; cin >> x >> y >> z;
add(x, y, z);
}
double l = 0, r = 1e6;
while (r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", l);
return 0;
}