单纯形被hack求助
  • 板块题目总版
  • 楼主ZnPdCo
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/4/13 11:57
  • 上次更新2024/4/13 14:25:28
查看原帖
单纯形被hack求助
560700
ZnPdCo楼主2024/4/13 11:57

在uoj上的单纯形模板,有一个hack数据把我的单纯形卡t了,只有97分,请问谷友有没有非特判的方法。

#include <bits/stdc++.h>
using namespace std;
#define N 100
#define ll long long
#define ld long double
#define eps 1e-8
#define inf 1e15
ll n, m, t;
ld a[N][N];
ll r[N];
ld ans[N];
std::mt19937 rnd(time(0));
void pivot(ll l, ll e) {
	swap(r[n + l], r[e]);
	ld t = a[l][e];
	a[l][e] = 1;
	for(ll i = 0; i <= n; i ++) a[l][i] /= t;
	for(ll i = 0; i <= m; i ++) if(i != l && abs(a[i][e]) > eps) {
		t = a[i][e]; a[i][e] = 0;
		for(ll j = 0; j <= n; j ++) {
			a[i][j] -= a[l][j] * t;
		}
	}
}
void init() {
	while(1) {
		ll l = 0, e = 0;
		for(ll i = 1; i <= m; i ++) {
			if(a[i][0] < -eps && (!l || rnd() % 2 == 0)) {
				l = i;
			}
		}
		if(!l) break;
		for(ll i = 1; i <= n; i ++) {
			if(a[l][i] < -eps && (!e || rnd() % 2 == 0)) {
				e = i;
			}
		}
		if(!e) {
			printf("Infeasible");
			exit(0);
		}
		pivot(l, e);
	}
}
void simplex() {
	while(1) {
		ll l = 0, e = 0;
		ld mn = inf;
		for(ll i = 1; i <= n; i ++) {
			if(a[0][i] > eps) {
				e = i;
				break;
			}
		}
		if(!e) break;
		for(ll i = 1; i <= m; i ++) {
			if(a[i][e] > eps && a[i][0] / a[i][e] < mn) {
				l = i;
				mn = a[i][0] / a[i][e];
			}
		}
		if(!l) {
			printf("Unbounded");
			exit(0);
		}
		pivot(l, e);
	}
}
int main() {
	scanf("%lld %lld %lld", &n, &m, &t);
	for(ll i = 1; i <= n; i ++) {
		scanf("%Lf", &a[0][i]);
	}
	for(ll i = 1; i <= m; i ++) {
		for(ll j = 1; j <= n; j ++) {
			scanf("%Lf", &a[i][j]);
		}
		scanf("%Lf", &a[i][0]);
	}
	for(ll i = 1; i <= n; i ++) r[i] = i;
	init();
	simplex();
	printf("%.8Lf\n", -a[0][0]);
	if(t) {
		for(ll i = 1; i <= m; i ++) ans[r[n + i]] = a[i][0];
		for(ll i = 1; i <= n; i ++) printf("%.8Lf ", ans[i]);
	}
}
Extra Test:
score: -3 Extra Test Failed : Time Limit Exceeded on 34
2024/4/13 11:57
加载中...