传送门
题意: 求无向图割集中平均边权最小的集合.
论文《最小割模型在信息学竞赛中的应用》原题.
分数规划. 每一条边取上的代价为 1.
- #include <bits/stdc++.h>
- using namespace std;
- inline int read() {
- int x = 0, f = 1; char ch = getchar();
- while (ch <'0' || ch> '9') { if (ch == '-') f = -1; ch = getchar(); }
- while (ch>= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
- return x * f;
- }
- const int N = 1e5 + 10;
- const double EPS = 1e-5;
- 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 = 1; i <= n; i++) iter[i] = head[i], level[i] = -1, vis[i] = 0;
- queue<int> que;
- que.push(1);
- level[1] = 0;
- 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] <0 && f) {
- level[v] = level[u] + 1;
- que.push(v);
- }
- }
- }
- return level[n] != -1;
- }
- double dfs(int u, double f) {
- if (u == n) return f;
- double flow = 0;
- for (int i = iter[u]; ~i; i = edge[i].next) {
- iter[u] = i;
- int v = edge[i].v;
- if (level[v] == level[u] + 1 && 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^1].f += w;
- if (f <= 0) break;
- }
- }
- return flow;
- }
- double dinic() {
- double ans = 0;
- while (bfs()) ans += dfs(1, 1e8);
- return ans;
- }
- bool check(double mid) {
- memset(head, -1, sizeof(head));
- cnt = 0;
- double flow = 0;
- for (int i = 1; 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] = 1;
- 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 = 1;
- while (~scanf("%d%d", &n, &m)) {
- if (kase> 1) puts("");
- kase = 2;
- for (int i = 1; i <= m; i++) {
- x[i] = read();y[i] = read();
- int a = read();z[i] = (double)a;
- }
- double l = 0, r = 1e7;
- while (r - l> EPS) {
- double mid = (l + r) / 2.0;
- if (check(mid)) l = mid;
- else r = mid;
- }
- check(r);
- get_ans(1);
- tol = 0;
- for (int i = 1; i <= m; i++) {
- if (vis[x[i]] + vis[y[i]] == 1 || z[i] <= r) {
- ans[++tol] = i;
- }
- }
- printf("%d\n", tol);
- for (int i = 1; i <= tol; i++) {
- if (i - 1) putchar(' ');
- printf("%d", ans[i]);
- }
- puts("");
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3073177.html