ZOJ 2676 Network Wars(网络流+分数规划)

时间:2021-01-24 17:15:27

传送门

题意:求无向图割集中平均边权最小的集合。

论文《最小割模型在信息学竞赛中的应用》原题。

分数规划。每一条边取上的代价为1。

#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
} const int N = 1e5 + ;
const double EPS = 1e-;
struct Edge { int v, next; double f; } edge[N];
int n, m, head[N], cnt, level[N], iter[N], x[N], y[N];
double z[N];
bool vis[N];
inline void add(int u, int v, double f) {
edge[cnt].v = v; edge[cnt].f = f; edge[cnt].next = head[u]; head[u] = cnt++;
edge[cnt].v = u; edge[cnt].f = f; edge[cnt].next = head[v]; head[v] = cnt++;
}
bool bfs() {
for (int i = ; i <= n; i++) iter[i] = head[i], level[i] = -, vis[i] = ;
queue<int> que;
que.push();
level[] = ;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v; double f = edge[i].f;
if (level[v] < && f) {
level[v] = level[u] + ;
que.push(v);
}
}
}
return level[n] != -;
} double dfs(int u, double f) {
if (u == n) return f;
double flow = ;
for (int i = iter[u]; ~i; i = edge[i].next) {
iter[u] = i;
int v = edge[i].v;
if (level[v] == level[u] + && edge[i].f) {
double w = dfs(v, min(f, edge[i].f));
//if (fabs(w) < EPS) continue;
f -= w;
flow += w;
edge[i].f -= w, edge[i^].f += w;
if (f <= ) break;
}
}
return flow;
} double dinic() {
double ans = ;
while (bfs()) ans += dfs(, 1e8);
return ans;
} bool check(double mid) {
memset(head, -, sizeof(head));
cnt = ;
double flow = ;
for (int i = ; i <= m; i++) {
if (z[i] > mid) add(x[i], y[i], z[i] - mid);
else flow += z[i] - mid;
}
flow += dinic();
return flow >= EPS;
} void get_ans(int u) {
vis[u] = ;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
if (!vis[v] && edge[i].f > EPS) {
get_ans(v);
}
}
}
int ans[N], tol; int main() {
int kase = ;
while (~scanf("%d%d", &n, &m)) {
if (kase > ) puts("");
kase = ;
for (int i = ; i <= m; i++) {
x[i] = read();y[i] = read();
int a = read();z[i] = (double)a;
}
double l = , r = 1e7;
while (r - l > EPS) {
double mid = (l + r) / 2.0;
if (check(mid)) l = mid;
else r = mid;
}
check(r);
get_ans();
tol = ;
for (int i = ; i <= m; i++) {
if (vis[x[i]] + vis[y[i]] == || z[i] <= r) {
ans[++tol] = i;
}
}
printf("%d\n", tol);
for (int i = ; i <= tol; i++) {
if (i - ) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
return ;
}