C++ 代码
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define ROF(i, a, b) for(int i = a; i >= b; i --)
#define mem(a, b) memset(a, b, sizeof a)
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e8;
int n, S = 0, t = 198, T = 199;
int x[100], y[100], z[100];
int head[200], nxt[80000], ver[80000], edge[80000], w[80000], incf[200], tot = 1;
int q[200], d[200], pre[200], ans, l, r;
bool inq[200];
bool spfa() {
mem(incf, 0), mem(d, 0xcf), l = 1, r = 0;
q[++r] = S, d[S] = 0, incf[S] = inf, inq[S] = 1;
while(l != r + 1) {
int x = q[l ++];
inq[x] = 0;
if(l == 200) l = 1;
for(int e = head[x]; e; e = nxt[e]) {
if(!edge[e]) continue;
int y = ver[e];
if(d[y] < d[x] + w[e]) {
d[y] = d[x] + w[e];
pre[y] = e;
incf[y] = min(incf[x], edge[e]);
if(!inq[y]) {
q[++r] = y;
inq[y] = 1;
if(r == 199) r = 0;
}
}
}
}
if(incf[T] == 0) return 0;
return 1;
}
void ek() {
ans += incf[T] * d[T];
for(int e = pre[T]; e; e = pre[ver[e ^ 1]]) {
edge[e] -= incf[T], edge[e ^ 1] += incf[T];
}
}
void add(int a, int b, int c, int d) {
ver[++tot] = b, nxt[tot] = head[a], head[a] = tot, edge[tot] = c, w[tot] = d;
ver[++tot] = a, nxt[tot] = head[b], head[b] = tot, edge[tot] = 0, w[tot] = -d;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int time = 0;
while(cin >> n) {
if(n == 0) break;
mem(head, 0), tot = 1, ans = 0;
time ++;
FOR(i, 1, n) {
cin >> x[3 * i - 2] >> y[3 * i - 2] >> z[3 * i - 2];
if(x[3 * i - 2] < y[3 * i - 2]) swap(x[3 * i - 2], y[3 * i - 2]);
x[3 * i - 1] = x[3 * i - 2], y[3 * i - 1] = z[3 * i - 2], z[3 * i - 1] = y[3 * i - 2];
if(x[3 * i - 1] < y[3 * i - 1]) swap(x[3 * i - 1], y[3 * i - 1]);
x[3 * i] = y[3 * i - 2], y[3 * i] = z[3 * i - 2], z[3 * i] = x[3 * i - 2];
if(x[3 * i] < y[3 * i]) swap(x[3 * i], y[3 * i]);
}
FOR(i, 1, 3 * n) {
add(S, i, inf, 0);
add(i, i + 3 * n, 1, z[i]);
FOR(j, 1, 3 * n) {
if((x[i] > x[j] && y[i] > y[j]) || (x[i] > y[j] && y[i] > x[j])) add(i + 3 * n, j, inf, 0);
}
}
FOR(i, 3 * n + 1, 6 * n) add(i, t, inf, 0);
add(t, T, 1, 0);
while(spfa()) ek();
cout << "Case " << time << ": maximum height = " << ans << '\n';
}
return 0;
}