看到这题目如果想费用流的话就 gg 了, 就像 LCA https://www.luogu.org/problemnew/show/P4211 这道题一样, 不要被题目迷惑......
我们考虑 Bob, 他想让总费用最大, 那么他的所有费用一定都加到流量最大的那一条边上. 而 Alice 想让总费用最小, 那么就是让流量最大的那一条边最小, 自然就想到二分边的容量啦!
不过这道题特殊的地方是要实数二分. 其实终止条件就是当 R - L 小于自己设定的一个精度. 然后如果当前不符合, 不应该是 L = mid + 1, 因为 (mid, mid + 1) 中很有可能是答案, 所以应该是 L = mid +eps.
第一次写实数二分, 总是死循环, 调了有那么一会儿......
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<algorithm>
- #include<cstring>
- #include<cstdlib>
- #include<cctype>
- #include<vector>
- #include<stack>
- #include<queue>
- using namespace std;
- #define enter puts("")
- #define space putchar(' ')
- #define Mem(a, x) memset(a, x, sizeof(a))
- #define rg register
- typedef long long ll;
- typedef double db;
- const int INF = 0x3f3f3f3f;
- const db eps = 1e-8;
- const int maxn = 105;
- inline ll read()
- {
- ll ans = 0;
- char ch = getchar(), last = ' ';
- while(!isdigit(ch)) {last = ch; ch = getchar();}
- while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
- if(last == '-') ans = -ans;
- return ans;
- }
- inline void write(ll x)
- {
- if(x <0) x = -x, putchar('-');
- if(x>= 10) write(x / 10);
- putchar(x % 10 + '0');
- }
- int n, m, p, Max;
- struct Edge
- {
- int from, to;
- db cap, flow;
- };
- vector<Edge> edges;
- vector<int> G[maxn];
- void addEdge(int from, int to, int w)
- {
- edges.push_back((Edge){from, to, (db)w, 0});
- edges.push_back((Edge){to, from, 0, 0});
- int sz = edges.size();
- G[from].push_back(sz - 2);
- G[to].push_back(sz - 1);
- }
- int dis[maxn];
- bool bfs()
- {
- Mem(dis, 0); dis[1] = 1;
- queue<int> q; q.push(1);
- while(!q.empty())
- {
- int now = q.front(); q.pop();
- for(int i = 0; i <(int)G[now].size(); ++i)
- {
- Edge& e = edges[G[now][i]];
- if(!dis[e.to] && e.cap> e.flow + eps)
- {
- dis[e.to] = dis[now] + 1;
- q.push(e.to);
- }
- }
- }
- return dis[n];
- }
- int cur[maxn];
- db dfs(int now, db res)
- {
- if(now == n || res == 0) return res;
- db flow = 0, f;
- for(int& i = cur[now]; i <(int)G[now].size(); ++i)
- {
- Edge& e = edges[G[now][i]];
- if(dis[e.to] == dis[now] + 1 && (f = dfs(e.to, min(res, e.cap - e.flow)))> 0)
- {
- e.flow += f;
- edges[G[now][i] ^ 1].flow -= f;
- flow += f; res -= f;
- if(res == 0) break;
- }
- }
- return flow;
- }
- db maxflow()
- {
- db flow = 0;
- while(bfs())
- {
- Mem(cur, 0);
- flow += dfs(1, (db)INF);
- }
- return flow;
- }
- void build_Gra(db x) // 不用重建, 修改每一条边的参数就行
- {
- for(int i = 0; i <(int)edges.size(); i += 2)
- {
- edges[i].cap = x; edges[i].flow = 0;
- edges[i ^ 1].cap = 0; edges[i ^ 1].flow = 0;
- }
- }
- int main()
- {
- n = read(); m = read(); p = read();
- for(int i = 1; i <= m; ++i)
- {
- int x = read(), y = read(), w = read();
- addEdge(x, y, w);
- }
- Max = maxflow();
- db L = 0, R = (db)INF;
- while(L < R - eps)
- {
- db mid = (L + R) / 2.00;
- build_Gra(mid);
- if(maxflow()> (db)Max - eps) R = mid;
- else L = mid + eps;
- }
- printf("%d %.6lf\n", Max, (L + R) / 2.00 * p);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2781506.html