【HDOJ】3315 My Brute

几乎与2853相同,Successive Shortest Path Algorithm(SSPA) 解费用流。

 /* 3315 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int INF = 0x1f1f1f1f;
const int maxn = ;
const int maxv = maxn*;
const int maxe = maxv * maxv * ;
int V[maxe], F[maxe], W[maxe], nxt[maxe];
int head[maxv], pre[maxv], ID[maxv], dis[maxv], cnt[maxv];
bool visit[maxv];
int Hi[maxn], Pi[maxn], Ai[maxn], Bi[maxn], Vi[maxn];
int s, t, m; bool win(int i, int j) {
int c1 = (Pi[j] + Ai[i] - ) / Ai[i];
int c2 = (Hi[i] + Bi[j] - ) / Bi[j]; return c1 <= c2;
} void addEdge(int u, int v, int c, int w) {
V[m] = v;
F[m] = c;
W[m] = w;
nxt[m] = head[u];
head[u] = m++; V[m] = u;
F[m] = ;
W[m] = -w;
nxt[m] = head[v];
head[v] = m++;
} void Bellman_Ford(int st, int ed) {
int u, v, k;
queue<int> Q; memset(dis, INF, sizeof(dis));
memset(cnt, , sizeof(cnt));
memset(pre, -, sizeof(pre));
dis[st] = ;
cnt[st] = ;
Q.push(st); while (!Q.empty()) {
u = Q.front();
Q.pop();
cnt[u] = -cnt[u];
for (k=head[u]; k!=-; k=nxt[k]) {
v = V[k];
if (F[k] && dis[v]>dis[u]+W[k]) {
dis[v] = dis[u] + W[k];
ID[v] = k;
pre[v] = u;
if (cnt[v] <= ) {
cnt[v] = -cnt[v] + ;
Q.push(v);
}
}
}
}
} bool bfs(int st, int ed) {
Bellman_Ford(st, ed);
priority_queue<pii, vector<pii>, greater<pii> > Q;
int u, v, k; Q.push(make_pair(, st));
while (!Q.empty()) {
pii p = Q.top();
Q.pop();
u = p.second;
if (dis[p.second] > p.first) continue;
if (u == ed) break;
for (k=head[u]; k!=-; k=nxt[k]) {
v = V[k];
if (F[k] && dis[v]>dis[u]+W[k]) {
dis[v] = dis[u] + W[k];
ID[v] = k;
pre[v] = u;
Q.push(make_pair(dis[v], v));
}
}
} return pre[ed] == -;
} int MCMF(int s, int t) {
int ret = , tmp;
int u, v, k; while () {
if (bfs(s, t))
break; tmp = INF;
for (v=t, u=pre[v]; v!=s; v=u, u=pre[v]) {
k = ID[v];
tmp = min(F[k], tmp);
} for (v=t, u=pre[v]; v!=s; v=u, u=pre[v]) {
k = ID[v];
F[k] -= tmp;
F[k^] += tmp;
} ret += dis[t] * tmp;
} return ret;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n;
int ans, tmp; while (scanf("%d", &n)!=EOF && n) {
rep(i, , n+)
scanf("%d", &Vi[i]);
rep(i, , n+)
scanf("%d", &Hi[i]);
rep(i, , n+)
scanf("%d", &Pi[i]);
rep(i, , n+)
scanf("%d", &Ai[i]);
rep(i, , n+)
scanf("%d", &Bi[i]); s = m = ;
t = n + n + ;
memset(head, -, sizeof(head)); rep(i, , n+) {
rep(j, , n+) {
if (win(i, j)) {
if (i == j) {
tmp = Vi[i] * + ;
} else {
tmp = Vi[i] * ;
}
} else {
if (i == j) {
tmp = -Vi[i] * + ;
} else {
tmp = -Vi[i] * ;
}
}
addEdge(i, n+j, , -tmp);
}
} rep(i, , n+) {
addEdge(s, i, , );
addEdge(n+i, t, , );
} ans = -MCMF(s, t);
if (ans < ) {
puts("Oh, I lose my dear seaco!");
} else {
printf("%d %.03f%%\n", ans/, ans%*100.0/n);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
上一篇:开始PYTHON之路


下一篇:PLSQL Develop 配置