本題過于簡單，朱劉算法模板題，考慮二分一下帶寬即可

• title
• code

title

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 65 #define MAXM 100005 #define int long long #define inf 0x3f3f3f3f struct node {int u, v, w, c;node(){}node( int U, int V, int W, int C ) {u = U, v = V, w = W, c = C;} }Edge[MAXM], edge[MAXM]; int vis[MAXN], id[MAXN], pre[MAXN], in[MAXN];int pigcow( int rt, int n, int m, int val ) {for( int i = 1;i <= m;i ++ )edge[i] = Edge[i];int ans = 0;while( 1 ) {for( int i = 0;i < n;i ++ ) in[i] = inf;for( int i = 1;i <= m;i ++ ) {if( edge[i].w < val ) continue;int u = edge[i].u, v = edge[i].v, c = edge[i].c;if( c < in[v] && u != v )pre[v] = u, in[v] = c;} for( int i = 0;i < n;i ++ ) {if( i == rt ) continue;if( in[i] == inf ) return inf;}int cnt = 0;in[rt] = 0;memset( id, -1, sizeof( id ) );memset( vis, -1, sizeof( vis ) ); for( int i = 0;i < n;i ++ ) {ans += in[i];int t = i;while( vis[t] != i && id[t] == -1 && t != rt )vis[t] = i, t = pre[t];if( t != rt && id[t] == -1 ) {for( int fa = pre[t];fa != t;fa = pre[fa] )id[fa] = cnt;id[t] = cnt ++;}}if( ! cnt ) break;for( int i = 0;i < n;i ++ )if( id[i] == -1 ) id[i] = cnt ++;for( int i = 1;i <= m;i ++ ) {if( edge[i].w < val ) continue;int u = edge[i].u, v = edge[i].v;edge[i].u = id[u], edge[i].v = id[v];if( id[u] != id[v] ) edge[i].c -= in[v];}n = cnt;rt = id[rt];}return ans; } signed main() {int n, m, T, cost;scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld %lld", &n, &m, &cost );int maxx = 0;for( int i = 1, u, v, w, c;i <= m;i ++ ) {scanf( "%lld %lld %lld %lld", &u, &v, &w, &c );Edge[i] = node( u, v, w, c );maxx = max( maxx, w );}int ans = -1, l = 1, r = maxx;while( l <= r ) {int mid = ( l + r ) >> 1;if( pigcow( 0, n, m, mid ) <= cost )ans = mid, l = mid + 1;elser = mid - 1;}if( ~ ans ) printf( "%lld kbps\n", ans );else printf( "streaming not possible.\n" );}return 0; }

總結

以上是生活随笔為你收集整理的[UVA - 11865]Stream My Contest（最小树形图+朱刘算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。