题目：My Brute
Seaco是一个漂亮的妹子，喜欢玩一款名叫My Brute的游戏。情人节快到了，starvae和xingxing都想邀请妹子过节，但是妹子只能陪一个啊，于是两个人决定打一架，用男人的方式对决，来一场My Brute吧！
一开始两个人都有n（n<100）只宠物，每个宠物有生命值，伤害值，每次两个人各派出一只宠物，starvae可以任意确定宠物的出场顺序，xingxing不可以。
每局开始starvae先打，hp<=0的一方输。
starvvae的第i个宠物（因为可以换顺序，也就是可能不是第i个出场的）赢vi分，否则减vi分。如果结束时starvae的分数大于0，starvae就赢了。
现在请你求出如果能赢，输出最大分数，和出场顺序和原顺序的相似度（如果最大分数有多种可能的安排方法，选择相似度最大的方法）。不能赢就输出Oh, I lose my dear seaco!
题解：@g3&wy%*￥…sd…#%…
我没做出来。。。因为窝读错题了。。。哭T^T。。。查题解不小心就查到了答案。。。我的英语绝对没救了。。。虽然不知道读对也不知道能不能做出来。。。。。
很好想的是源点连每一个starvae的宠物，流量是1，权值为0，xingxing的每个宠物的连汇点，流量是1，权值为0，两个人的宠物两两相连，能赢权值是v[i]，否则是-v[i]。
但是这里求得是最大值，以前也做过求最大值，方法是加边加-w，但这里不行，因为边本来就是有正有负。
所以每次spfa求最短路改为求最长路。记得初始化时是-inf。
还有一个问题是。。。如何保证尽可能原顺序。。。于是有一个比较巧妙的方法，就是把所有v[i]*100，然后把每一个顺序不变的边，权值+1，因为点的个数是100以内的，所以能保证结果正确。。
#include <cstring>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long ll; const int MAXV = ;
const int INF = <<; struct Edge { int to, cap, cost, rev; };
vector<Edge> G[MAXV];
int dist[MAXV], prv[MAXV], pre[MAXV], in[MAXV];
queue<int> que; void addedge(int from, int to, int cap, int cost) {
G[from].push_back((Edge){to, cap, cost, G[to].size()});
G[to].push_back((Edge){from, , -cost, G[from].size()-});
} int min_cost_max_flow(int s, int t) { //, int f) {
int res = ;
int f = ;
while () { //f > 0) {
for (int i = ; i <= t; ++i) dist[i] = -INF, in[i] = ;
dist[s] = ;
while (!que.empty()) que.pop();
in[s] = ;
que.push(s); while (!que.empty()) {
int u = que.front(); que.pop(); in[u] = ;
for (int i = ; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > && dist[e.to] < dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prv[e.to] = u;
pre[e.to] = i;
if (in[e.to] == ) {
in[e.to] = ;
que.push(e.to);
}
}
}
} if (dist[t] == -INF) break; //return -1; int d = INF; // d = f;
for (int v = t; v != s; v = prv[v]) {
d = min(d, G[prv[v]][pre[v]].cap);
}
f += d;
res += d * dist[t];
for (int v = t; v != s; v = prv[v]) {
Edge &e = G[prv[v]][pre[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
} const int N = ;
int v[N], h[N], p[N], a[N], b[N]; bool win(int h, int p, int a, int b) { // hp damage
int x = h/b; if (h % b != ) x++;
int y = p/a; if (p % a != ) y++;
return x >= y;
} int main()
{
int n;
while (~scanf("%d", &n) && n) {
for (int i = ; i < n; ++i) scanf("%d", &v[i]);
for (int i = ; i < n; ++i) scanf("%d", &h[i]);
for (int i = ; i < n; ++i) scanf("%d", &p[i]);
for (int i = ; i < n; ++i) scanf("%d", &a[i]);
for (int i = ; i < n; ++i) scanf("%d", &b[i]); int src = , sink = n+n+; for (int i = src; i <= sink; ++i) G[i].clear(); for (int i = ; i < n; ++i) {
for (int j = ; j < n; ++j) {
int tmp = win(h[i], p[j], a[i], b[j]) ? v[i] : -v[i];
tmp *= ; if (i == j) tmp++;
addedge(i+, n+j+, , tmp);
}
} for (int i = ; i < n; ++i) {
addedge(src, i+, , );
addedge(i++n, sink, , );
} int ans = min_cost_max_flow(src, sink); if (ans/ <= ) printf("Oh, I lose my dear seaco!\n");
else printf("%d %.3f%%\n", ans/, ans%/(double)n*); }
return ;
}
既然很明显是二分图
所以可以考虑一下KM解法，建图什么的都一样辣，速度还是一如既往的完爆费用流。。
#include <cstring>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = ;
const int INF = 0x3f3f3f3f; int G[MAXN][MAXN];
int vx[MAXN], vy[MAXN];
bool visx[MAXN], visy[MAXN];
int match[MAXN];
int slack[MAXN]; int N; bool dfs(int x)
{
visx[x] = true; for (int y = ; y < N; ++y) { if (visy[y]) continue; int gap = vx[x] + vy[y] - G[x][y]; if (gap == ) {
visy[y] = true;
if (match[y] == - || dfs( match[y] )) {
match[y] = x;
return true;
}
} else {
slack[y] = min(slack[y], gap);
}
} return false;
} int KM()
{
memset(match, -, sizeof match);
memset(vy, , sizeof vy); for (int i = ; i < N; ++i) {
vx[i] = G[i][];
for (int j = ; j < N; ++j) {
vx[i] = max(vx[i], G[i][j]);
}
} for (int i = ; i < N; ++i) { fill(slack, slack + N, INF); while () {
memset(visx, false, sizeof visx);
memset(visy, false, sizeof visy); if (dfs(i)) break; int d = INF;
for (int j = ; j < N; ++j)
if (!visy[j]) d = min(d, slack[j]); for (int j = ; j < N; ++j) {
if (visx[j]) vx[j] -= d;
if (visy[j]) vy[j] += d;
else slack[j] -= d;
}
}
} int res = ;
for (int i = ; i < N; ++i)
res += G[ match[i] ][i]; return res;
} int v[MAXN], h[MAXN], p[MAXN], a[MAXN], b[MAXN]; bool win(int h, int p, int a, int b) { // hp damage
int x = h/b; if (h % b != ) x++;
int y = p/a; if (p % a != ) y++;
return x >= y;
} int main()
{
int n;
while (~scanf("%d", &n) && n) { N = n;
for (int i = ; i < n; ++i) scanf("%d", &v[i]);
for (int i = ; i < n; ++i) scanf("%d", &h[i]);
for (int i = ; i < n; ++i) scanf("%d", &p[i]);
for (int i = ; i < n; ++i) scanf("%d", &a[i]);
for (int i = ; i < n; ++i) scanf("%d", &b[i]); for (int i = ; i < n; ++i) {
for (int j = ; j < n; ++j) {
int tmp = win(h[i], p[j], a[i], b[j]) ? v[i] : -v[i];
tmp *= ; if (i == j) tmp++;
G[i][j] = tmp;
}
} int ans = KM(); if (ans/ <= ) printf("Oh, I lose my dear seaco!\n");
else printf("%d %.3f%%\n", ans/, ans%/(double)n*); }
return ;
}