题目大意

给你一个$n$个点$m$条带权双向边的图，求选取割的集合，最小化$$\frac{\sum_{i\in cut}c_i}{|cut|}$$

简要题解

01分数规划，先二分答案，然后把边权设为$c[i]-ans$，如果这个值小于0，显然要选这个边，再加上最小割的值，如果这个和小于0，则说明二分的答案太大，否则太小。

最后输出结果，方法是先bfs得到S集合，然后横跨S和T的边在割中。

1 #include 
     
        2 using namespace std;  3 namespace my_header {  4 #define pb push_back  5 #define mp make_pair  6 #define pir pair
      
         7 #define vec vector
       
          8 #define pc putchar  9 #define clr(t) memset(t, 0, sizeof t) 10 #define pse(t, v) memset(t, v, sizeof t) 11 #define bl puts("") 12 #define wn(x) wr(x), bl 13 #define ws(x) wr(x), pc(' ') 14     typedef long long LL; 15     typedef double DB; 16     inline char gchar() { 17         char ret = getchar(); 18         for(; (ret == '\n' || ret == '\r' || ret == ' ') && ret != EOF; ret = getchar()); 19         return ret; } 20     template
        
          inline void fr(T &ret, char c = ' ', int flg = 1) { 21         for(c = getchar(); (c < '0' || '9' < c) && c != '-'; c = getchar()); 22         if (c == '-') { flg = -1; c = getchar(); } 23         for(ret = 0; '0' <= c && c <= '9'; c = getchar()) 24             ret = ret * 10 + c - '0'; 25         ret = ret * flg; } 26     inline int fr() { int t; fr(t); return t; } 27     template
         
           inline void fr(T&a, T&b) { fr(a), fr(b); } 28     template
          
            inline void fr(T&a, T&b, T&c) { fr(a), fr(b), fr(c); } 29 template
           
             inline char wr(T a, int b = 10, bool p = 1) { 30 return a < 0 ? pc('-'), wr(-a, b, 0) : (a == 0 ? (p ? pc('0') : p) : 31 (wr(a/b, b, 0), pc('0' + a % b))); 32 } 33 template
            
              inline void wt(T a) { wn(a); } 34 template
             
               inline void wt(T a, T b) { ws(a), wn(b); } 35 template
              
                inline void wt(T a, T b, T c) { ws(a), ws(b), wn(c); } 36 template
               
                 inline void wt(T a, T b, T c, T d) { ws(a), ws(b), ws(c), wn(d); } 37 template
                
                  inline T gcd(T a, T b) { 38 return b == 0 ? a : gcd(b, a % b); } 39 template
                 
                   inline T fpw(T b, T i, T _m, T r = 1) { 40 for(; i; i >>= 1, b = b * b % _m) 41 if(i & 1) r = r * b % _m; 42 return r; } 43 }; 44 using namespace my_header; 45 46 static const int maxE = 200000, maxV = 2000 + 100; 47 static const double EPS = 1e-6; 48 static const double INF = 2e8; 49 struct MaxFlow { 50 int e, h[maxV], to[maxE], nxt[maxE]; 51 double cap[maxE]; 52 void init() { 53 memset(h, -1, sizeof h); 54 e = 0; 55 } 56 void addEdge(int u,int v, double c) { 57 to[e] = v, nxt[e] = h[u], cap[e] = c, h[u] = e++; 58 to[e] = u, nxt[e] = h[v], cap[e] = c, h[v] = e++; 59 } 60 61 int dis[maxV], que[maxE * 20], qh, qt; 62 bool inq[maxV]; 63 int s, t; 64 65 int sgn(double x) { 66 return x < -EPS ? -1 : EPS < x; 67 } 68 69 bool bfs() { 70 que[qh = qt = 0] = s; 71 memset(inq, 0, sizeof inq); 72 memset(dis, 0x3f, sizeof dis); 73 dis[s] = 0; 74 inq[s] = 1; 75 while (qh <= qt) { 76 int u = que[qh++]; 77 for (int i = h[u]; i != -1; i = nxt[i]) 78 if (cap[i] > EPS && !inq[to[i]]) { 79 int v = to[i]; 80 inq[v] = 1; 81 dis[v] = dis[u] + 1; 82 que[++qt] = v; 83 } 84 } 85 return dis[t] != 0x3f3f3f3f; 86 } 87 88 double dfs(int u, double a = 0) { 89 if (u == t || sgn(a) == 0) 90 return a; 91 double flow = 0, f; 92 for (int i = h[u]; i != -1; i = nxt[i]) 93 if (dis[to[i]] == dis[u]+1 && (f = dfs(to[i], min(a, cap[i]))) > 0) { 94 flow += f; 95 cap[i] -= f; 96 cap[i^1] += f; 97 a -= f; 98 //if (a == 0) break; 99 if (a == 0) {100 return flow;101 }102 }103 dis[u] = -1;104 // 原来我写了两年的网络流算法都是错的 = = 膜拜wmj大爷105 return flow;106 }107 108 double maxFlow() {109 double flow = 0;110 while (bfs())111 flow += dfs(s, INF);112 return flow;113 }114 } mf;115 116 const int MAXM = 500;117 int n, m;118 int u[MAXM], v[MAXM], w[MAXM];119 120 121 int main() {122 #ifdef lol123 freopen("G.in", "r", stdin);124 freopen("G.out", "w", stdout);125 #else126 freopen("network.in", "r", stdin);127 freopen("network.out", "w", stdout);128 #endif129 fr(n, m);130 for (int i = 1; i <= m; ++i)131 fr(u[i], v[i], w[i]);132 double l = 0, r = 2e7, c;133 while (r - l > 1e-7) {134 c = (l + r) / 2;135 mf.init();136 mf.s = 1, mf.t = n;137 double t = 0;138 for (int i = 1; i <= m; ++i)139 if (w[i] - c > EPS)140 mf.addEdge(u[i], v[i], w[i] - c);141 else if (w[i] - c < -EPS)142 t += w[i] - c;143 t += mf.maxFlow();144 if (t < EPS)145 r = c;146 else l = c;147 }148 c = (l + r) / 2;149 vector
                  
                    ans;150 for (int i = 1; i <= m; ++i) {151 if (w[i] - c < EPS || (mf.inq[u[i]] ^ mf.inq[v[i]]))152 ans.pb(i);153 }154 wt(ans.size());155 for (auto &&k : ans)156 ws(k);157 bl;158 159 return 0;160 }