ZOJ_2676
这个题目可以像最优比率生成树那样用0-1分数规划去做，只不过最优比率生成树每次是求一棵生成树，而这个题目要求一个最小割。
对于每次二分，在建图的时候可能会出现边权为负的边，由于通过分析后可知这些边一定会选，所以就没必要再将其加入到新建的图中了。
最后要输出最小割集，求最小割集的时候可以用DFS遍历做完最大流之后的图，且只能沿没有满流的边向下走。遍历完成后，如果某条边有一个端点遍历到了而另外一个端点没有遍历到，那么就说明这条边是属于最小割集中的。
#include#include #include #define zero 1e-8#define MAXD 110#define MAXM 1610#define INF 0x3f3f3f3fusing namespace std;int N, M, S, T, first[MAXD], work[MAXD], e, next[MAXM], v[MAXM], id[MAXM], use[MAXM], vis[MAXD], q[MAXD], d[MAXD];double flow[MAXM];struct Graph{ int u[MAXM], v[MAXM], w[MAXM], id[MAXM], e; void init() { e = 0; } void add(int x, int y, int z, int flag) { u[e] = x, v[e] = y, w[e] = z, id[e] = flag; ++ e; }}g;void init(){ int i, x, y, z; g.init(); for(i = 1; i <= M; i ++) { scanf("%d%d%d", &x, &y, &z); g.add(x, y, z, i); }}void add(int x, int y, double f, int flag){ v[e] = y, flow[e] = f, id[e] = flag; next[e] = first[x], first[x] = e ++;}double initgraph(double r){ int i; double ans = 0; memset(use, 0, sizeof(use)); memset(first, -1, sizeof(first)); e = 0; for(i = 0; i < g.e; i ++) { if(g.w[i] - r <= zero) use[g.id[i]] = 1, ans += g.w[i] - r; else { add(g.u[i], g.v[i], g.w[i] - r, g.id[i]), add(g.v[i], g.u[i], 0, g.id[i]); add(g.v[i], g.u[i], g.w[i] - r, g.id[i]), add(g.u[i], g.v[i], 0, g.id[i]); } } return ans;}int bfs(){ int i, j, rear = 0; memset(d, -1, sizeof(d)); d[S] = 0, q[rear ++] = S; for(i = 0; i < rear; i ++) for(j = first[q[i]]; j != -1; j = next[j]) if(flow[j] > zero && d[v[j]] == -1) { d[v[j]] = d[q[i]] + 1; if(v[j] == T) return 1; q[rear ++] = v[j]; } return 0;}double dfs(int cur, double a){ if(cur == T) return a; double t; for(int &i = work[cur]; i != -1; i = next[i]) if(flow[i] > zero && d[v[i]] == d[cur] + 1) if((t = dfs(v[i], flow[i] < a ? flow[i] : a)) > zero) { flow[i] -= t; flow[i ^ 1] += t; return t; } return 0;}double dinic(){ double ans = 0, t; while(bfs()) { memcpy(work, first, sizeof(first)); while((t = dfs(S, INF)) > zero) ans += t; } return ans;}void DFS(int cur){ int i; vis[cur] = 1; for(i = first[cur]; i != -1; i = next[i]) if(flow[i] > zero && !vis[v[i]]) DFS(v[i]);}void print(){ int i, j, n = 0, flag = 0; memset(vis, 0, sizeof(vis)); DFS(S); for(i = 1; i < N; i ++) for(j = first[i]; j != -1; j = next[j]) if((vis[i] & !vis[v[j]]) || (!vis[i] && vis[v[j]])) use[id[j]] = 1; for(i = 1; i <= M; i ++) if(use[i]) ++ n; printf("%d\n", n); for(i = 1; i <= M; i ++) if(use[i]) { flag ? printf(" ") : flag = 1; printf("%d", i); } printf("\n");}void solve(){ int i; double ans, min, max, mid; max = 10000010, min = 0; S = 1, T = N; for(i = 0; i < 50; i ++) { mid = (min + max) / 2; ans = initgraph(mid); ans += dinic(); if(ans > 0) min = mid; else max = mid; } print();}int main(){ while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0;}