Original link: https://www.shuizilong.com/house/archives/luogu-p4412-shoi2004%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0 %91/
The main troublesome point of this question is to find the ring. . .
const int N = 50 + 9, M = int(1.5e3) + 9; struct Graph { int id[N][N]; struct edge { int x, y, w; void in() { RD(x, y, w); } } E[M]; int n, m; void in() { RD(n, m); REP_1(i, m) { E[i].in(); id[E[i].x][E[i].y] = id[E[i].y][E[i].x] = i; } } } G; struct Tree { VI adj[N]; int fa[N], dep[N]; void dfs(int u = 1, int p = -1) { for (auto v: adj[u]) if (v != p) { fa[v] = u; dep[v] = dep[u] + 1; dfs(v, u); } } void in() { DO(Gn-1) { int x, y; RD(x, y); adj[x].PB(y); adj[y].PB(x); } dfs(); } } T; struct Simplex { const static int N = ::M, M = int(1e3) + 9; DB a[N+1][M+1]; int n, m; void pivot(int in, int out) { REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //reset out constraint a[out][in] = 1/a [out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //Recalculate other constraints DB t = a[i][in]; a[i][in ] = 0; REP(j, m+1) a[i][j] += t*a[out][j]; } } DB run() { while (true) { int in=0, out=0; DB Min=OO; REP_1(i, m) if(sgn(a[0][i])>0) { in=i; break; } if(!in)return a[0][0]; REP_1(i, n) if(sgn(a[i][in])<0&&a[i][0]/-a[i][in]<Min) { Min=a[i][0]/-a[i][in]; out=i; } if(!out)throw; //unbounded pivot(in, out); } } int gao() { // zb // c A G.in(); T.in(); n = Gm; m = 0; REP_1(i, n) { a[i][0] = 1; int u = GE[i].x, v = GE[i].y; if (T.dep[u] < T.dep[v]) swap(u, v); if (T.fa[u] != v) { // E[i] is not a tree edge while (u != v) { int p = T.fa[u]; int j = G.id[p][u]; // E[j] is a tree edge if (GE[i].w < GE[j].w) { ++m; a[i][m] = a[j][m] = -1; a[0][m] = GE[j].w - GE[i].w; } u = p; if (T.dep[u] < T.dep[v]) swap(u, v); } } } return run(); } } fst; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif OT(fst.gao()); }
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p4412-shoi2004%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0 %91/
This site is for inclusion only, and the copyright belongs to the original author.