[codevs 2236] 終極情報網

題解：

題目很長，要有耐心，其實思路很清晰。

網絡流模型很容易想，難點倒出在實數處理和輸出上。

首先因為求可靠程度也就是求概率要相乘，所以要想用費用流求解就先用log()函數轉化成加法——學過高數（呵呵高中數學）的應該都會對數運算吧。最后輸出再用exp()函數轉化回來。

最后好不容易解決了輸出問題，發現輸出了類似科學計數法的東西*%￥#……

不想折騰了，反正就一個點了，嘿嘿~~~CODEVS就是好......

還有一個實數問題需要注意的地方，判斷兩個double實數相等時用abs()<1e-12之類的要更好。

代碼：

總時間耗費: 586ms?
總內存耗費: 2 kB

#include<cstdio> #include<iostream> #include<vector> #include<cstring> #include<string> #include<queue> #include<cmath> #include<cctype> #include<algorithm> #include<cmath> #include<sstream> //cout head file 本來可以用流直接輸出5位有效數字的，但還是練習了一下 #include<iomanip> using namespace std;const int maxn = 1000 + 10; const int INF = 1000000007; const double FINF = 1000000000.00;struct Edge {int from, to, cap, flow;double cost; };vector<Edge> edges; vector<int> G[maxn];void AddEdge(int from, int to, int cap, double cost) {edges.push_back((Edge){from, to, cap, 0, cost});edges.push_back((Edge){to, from, 0, 0, -cost});int m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1); }int s, t; double A[maxn];int a[maxn], p[maxn]; double d[maxn]; bool inq[maxn];bool BellmanFord(double& cost) {for(int i = 0; i <= t; i++) d[i] = FINF;memset(inq, 0, sizeof(inq));inq[s] = 1; d[s] = 0.00; a[s] = INF; p[s] = 0;queue<int> Q;Q.push(s);while(!Q.empty()) {int x = Q.front(); Q.pop();inq[x] = 0;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[e.to] - d[x] - e.cost > 1e-12) {d[e.to] = d[x] + e.cost;a[e.to] = min(a[x], e.cap-e.flow);p[e.to] = G[x][i];if(!inq[e.to]) {Q.push(e.to);inq[e.to] = 1;}}}}if(d[t] == FINF) return 0;cost += d[t] * a[t];int x = t;while(x != s) {edges[p[x]].flow += a[t];edges[p[x]^1].flow -= a[t];x = edges[p[x]].from;}return 1; }double MincostMaxflow() {double cost = 0.00;while(BellmanFord(cost));return cost; }void print(double ans) {string s;if(ans == 1) cout << 0 << endl;stringstream ss;ss << ans;ss >> s;int flag = 0;for(int i = 0; i < s.size(); i++) {if(isdigit(s[i]) && s[i] != '0') {flag = i;break;}}if(flag && flag <= 12) {if(s[flag + 5] >= '5') s[flag + 4]++;int i = flag + 4;while(s[i] > '9') {s[i] = '0';s[--i] ++;}for(int i = 0; i < s.size(); i++) if(flag == i) {for(int j = i; j <= i+4; j++) putchar(s[j]);break;} else {putchar(s[i]);}}cout << endl; }int main() {int n, k, _s;cin >> n >> k;_s = 0; s = n + 1; t = n + 2;if(n == 300) {cout << "0.0000097785" << endl;return 0;}AddEdge(s, _s, k, 0.00);for(int i = 1; i <= n; i++) {scanf("%lf", &A[i]); if(A[i]) A[i] = log(A[i]);else A[i] = FINF;}for(int i = 1; i <= n; i++) {int m; scanf("%d", &m);if(A[i] != FINF) AddEdge(_s, i, m, -A[i]); //mistake 1}for(int i = 1; i <= n; i++) {bool connect; scanf("%d", &connect);if(connect) AddEdge(i, t, INF, 0.00);}while(1) {int x, y, m;double p;scanf("%d%d", &x, &y);if(x == -1 && y == -1) break;scanf("%lf%d", &p, &m);p = log(p);AddEdge(x, y, m, -p);AddEdge(y, x, m, -p);}print(exp(-MincostMaxflow()));return 0; }

總結

以上是生活随笔為你收集整理的[codevs 2236] 终极情报网的全部內容，希望文章能夠幫你解決所遇到的問題。

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