Delivery Bears CodeForces - 653D(二分 + 网络流)

本文主要是介绍Delivery Bears CodeForces - 653D(二分 + 网络流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;typedef long long ll;const ll maxn = 1020;    // 点的数量 
const ll inf = 0x3f3f3f3f;   
ll n, m, x;struct Dinic {struct Edge {ll from, to, cap, flow;};ll s,t;vector<Edge> edges;vector<ll> G[maxn];ll d[maxn];bool vis[maxn];ll cur[maxn];void addEdge(ll from, ll to, ll cap) {edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){to,from,0,0});ll tt = edges.size();G[from].push_back(tt-2);G[to].push_back(tt-1);}bool BFS() {memset(vis, 0, sizeof(vis));queue<ll>Q;Q.push(s);d[s] = 0;vis[s] = 1;while(!Q.empty()) {ll x = Q.front(); Q.pop();for(ll i = 0; i < G[x].size(); i++) {Edge & e = edges[G[x][i]];if(!vis[e.to] && e.cap > e.flow) {vis[e.to] = 1;d[e.to] = d[x] + 1;Q.push(e.to);}}}return vis[t];}ll DFS(ll x, ll a) {if(x == t || a == 0) return a;ll flow = 0, f;for(ll & i =  cur[x]; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow))) > 0) {e.flow += f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0) break;}}return flow;}ll MF(ll s, ll t) {this->s = s; this->t = t;ll flow = 0;while(BFS()) {memset(cur, 0, sizeof(cur));flow += DFS(s, inf);}return flow;}void init() {for(ll i = 0; i <= n; i++) G[i].clear();edges.clear();}
}dinic;
struct E {ll u, v, w;E(ll u = 0, ll v = 0, ll w = 0) : u(u), v(v), w(w) {}
}; vector<E> es;bool judge(double mid)
{dinic.init();ll S = 0, T = n + 1;for(ll i = 0; i < m; i++) {dinic.addEdge(es[i].u, es[i].v, min((ll)(es[i].w / mid), x) );}dinic.addEdge(S, 1, x);dinic.addEdge(n, T, inf);return x == dinic.MF(S, T);
}
int main()
{ios::sync_with_stdio(false); cin.tie(0);cin >> n >> m >> x;for(ll i = 0; i < m; i++) {ll u, v, c;cin >> u >> v >> c;es.push_back(E(u, v, c));}double l = 0, r = 1e6;ll T = 1000;while(T--) {double mid = (l + r) / 2;if(judge(mid)) {l = mid;}else r = mid;}printf("%.10f", x * (l + r) / 2 );return 0;
}