Luogu P4412. [SHOI2004] Minimum Spanning Tree

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/

blank.jpg

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.

Leave a Comment