首先纠正:题目描述中应该是dx - y(这个式子本应该是从原题中证出来的)
题目描述:
给定一个平面上的一些有向边,每条边涂色费用为 \(dx-y\) , 其中 \(d\) 为边的长度(实数), \(x,y\) 为题中给定参数。环路的涂色费用为其上各边涂色费用和。找出一些环路,这些环路没有边相交,且环路涂色费用总和最大。
数据范围:
点数 \(n <= 100\),
\(x, y <= 1000\)
主要思路:最大费用循环流
对于最大费用循环流问题,我们先转化成最小费用循环流问题,这样便于套我们所学过的最小费用最大流模板。
转化:
对于边\(e(i, j, w, c)\),如果 \(c >= 0\),就正常的连\(e(i, j, w, c)\)的一条弧,如果 \(c < 0\),就建立源点\(s\)汇点\(t\),连接\(e(s, j, w, 0)\),\(e(j, t, w, 0)\),\(e(j, i, w, -c)\),用一个\(sum += c\)
最终 \((ans + mincost)\)就是最小费用循环流。
有点细节要注意,我们在最后输出答案时要记得加个大于0的比较小的数,如\(1e-7\),还要记得清\(sum\)
code:
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; #define go(i, j, n, k) for(int i = j; i <= n; i += k) #define fo(i, j, n, k) for(int i = j; i >= n; i -= k) #define rep(i, x) for(int i = h[x]; i != -1; i = e[i].nxt) #define curep(i, x) for(int i = cur[x]; i != -1; i = e[i].nxt) #define mn 100010 #define inf 1 << 30 #define ll long long inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int n, m; struct edge { int v, nxt, w; double d; } e[mn << 1]; int h[mn], p = -1; inline void add(int a, int b, int c, double d) { e[++p].nxt = h[a], h[a] = p, e[p].v = b, e[p].w = c, e[p].d = d; } inline void add_flow(int a, int b, int c, double d) { add(a, b, c, d), add(b, a, 0, -1.000 * d); } double dis[mn]; int flow[mn], vis[mn]; struct node { int v, id; } pre[mn]; inline bool SPFA(int s, int t) { go(i, 0, n, 1) dis[i] = 100000.0000, flow[i] = inf, vis[i] = 0, pre[i].v = pre[i].id = -1; queue<int> q; q.push(s), dis[s] = 0, vis[s] = 1; while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; rep(i, x) { int v = e[i].v, w = e[i].w; double d = e[i].d; if(w && dis[v] > dis[x] + d) { dis[v] = dis[x] + d, flow[v] = min(flow[x], w); pre[v].v = x, pre[v].id = i; if(!vis[v]) q.push(v), vis[v] = 1; } } } return pre[t].v != -1 ? 1 : 0; } inline void MCMF(int s, int t, int &maxflow, double &mincost) { while(SPFA(s, t)) { maxflow += flow[t]; mincost += flow[t] * dis[t]; for(int i = t; i != s; i = pre[i].v) e[pre[i].id].w -= flow[t], e[pre[i].id ^ 1].w += flow[t]; } } const int maxn = 111; int N, X, Y, x[maxn], y[maxn]; vector<int> conn[maxn]; inline int x2(int x) { return x * x; } inline double dist(int i, int j) { return sqrt((double)x2(x[i] - x[j]) + (double)x2(y[i] - y[j])); } double sum = 0.000; int du[mn]; int cas; inline void solve() { X = read(), Y = read(); go(i, 1, N, 1) { x[i] = read(), y[i] = read(); int tmp = read(); while(tmp != 0) conn[i].push_back(tmp), tmp = read(); } double ww = 0.000; go(i, 1, N, 1) { int siz = conn[i].size(); go(j, 0, siz - 1, 1) { ww = dist(i, conn[i][j]); double www = (Y * 1.000) - ww * (X * 1.000); if(www > 0) add_flow(i, conn[i][j], 1, www); else { add_flow(conn[i][j], i, 1, -www); sum += www; du[conn[i][j]]++, du[i]--; } } } int s = 0, t = N + 1; n = N + 1; go(i, 1, N, 1) { if(du[i] > 0) add_flow(s, i, du[i], 0.000); if(du[i] < 0) add_flow(i, t, -du[i], 0.000); } int mf = 0; double mc = 0.000; MCMF(s, t, mf, mc); printf("Case %d: ", ++cas); printf("%.2lf\n", -(mc + sum) + 1e-8); } inline void init() { memset(h, -1, sizeof h); p = -1; memset(x, 0, sizeof x); memset(y, 0, sizeof y); memset(conn, 0, sizeof conn); memset(dis, 0, sizeof dis); memset(vis, 0, sizeof vis); memset(flow, 0, sizeof flow); sum = 0.0000; memset(du, 0, sizeof du); } int main() { while(1) { N = read(); if(N == 0) break; init(); solve(); } return 0; }