Coding Contest HDU - 5988

題意：

有n個(gè)點(diǎn)，m個(gè)邊，每個(gè)點(diǎn)有人數(shù)和食物數(shù)，每個(gè)人都要吃一份食物，如果該點(diǎn)的食物不夠，他們就要去其他點(diǎn)，每個(gè)邊最多只能走c次，每次有人走一條路，這條路就有p的概率壞掉。第一個(gè)人通過(guò)時(shí)不會(huì)壞掉。求最小破壞的電線的概率

題解：

不難看出是一個(gè)網(wǎng)絡(luò)流，但是不知道該怎么建邊(這也是網(wǎng)絡(luò)流最難的部分)
參考題解
每條邊都有走的次數(shù)(當(dāng)作流量)，每個(gè)邊走一次發(fā)生破壞的概率為p(流量1，費(fèi)用p),我們開(kāi)始建立費(fèi)用流圖。根據(jù)題意每個(gè)邊壞掉概率，如果走多個(gè)邊那概率應(yīng)該相乘，但是費(fèi)用流往往是累加的，如何將相乘轉(zhuǎn)成累加？我們可以通過(guò)對(duì)每個(gè)概率取log當(dāng)成費(fèi)用，在log下所有都是相加減。
但是題目的概率都是小于1的，如果取log都是負(fù)數(shù)，費(fèi)用為負(fù)，這跑出來(lái)有問(wèn)題（跑出來(lái)的費(fèi)用會(huì)朝著更小走）。如何解決？那么取個(gè)負(fù)數(shù)呢，還是不行，因?yàn)槿∝?fù)后最小的變成最大的，跑出來(lái)就成最大費(fèi)用了
此時(shí)我們應(yīng)該這樣考慮，題目要求求最小概率，也就是1-最大概率，因此我們把每條邊的概率賦值為1-p，然后取反取log，這樣跑正好得到的是最小費(fèi)用，取出來(lái)之后再用1減去就好了
add(u,v,f,-log2(1-p)),f為容量，p為概率，從u到v的邊
其他如何建邊：
建立源點(diǎn)s，匯點(diǎn)t，對(duì)于S>B（人多），從源點(diǎn)連一條流量為S[i]-B[i]，費(fèi)用為0，對(duì)于s<b（糧食多)的，從該點(diǎn)向t連個(gè)邊，費(fèi)用為B[i]-S[i]
題目還說(shuō)第一次踩不會(huì)壞，所以從原有的邊取一條出來(lái)，流量為1，費(fèi)用為0

代碼：

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<string> #include<functional> typedef long long LL; using namespace std; #define MAXN 110 #define MAXM 25000 #define ll l,mid,now<<1 #define rr mid+1,r,now<<1|1 #define lson l1,mid,l2,r2,now<<1 #define rson mid+1,r1,l2,r2,now<<1|1 #define pi acos(-1.0) #define INF 2e9 const double eps = 1e-8; const int mod = 1e9 + 7; struct Edge {int to, next, cap, flow;double cost; }edge[MAXM]; int head[MAXN], tol; int pre[MAXN]; double dis[MAXN]; bool vis[MAXN]; int N;//節(jié)點(diǎn)總個(gè)數(shù)，節(jié)點(diǎn)編號(hào)從0~N-1 void init(int n) {N = n;tol = 0;memset(head, -1, sizeof(head)); } void addedge(int u, int v, int cap, double cost) {edge[tol].to = v;edge[tol].cap = cap;edge[tol].cost = cost;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = 0;edge[tol].cost = -cost;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++; } bool spfa(int s, int t) {queue<int>q;for (int i = 0; i <= N; i++){dis[i] = INF;vis[i] = false;pre[i] = -1;}dis[s] = 0;vis[s] = true;q.push(s);while (!q.empty()){//cout<<1<<endl; int u = q.front();q.pop();vis[u] = false;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (edge[i].cap > edge[i].flow &&dis[v]-dis[u]-edge[i].cost>eps){dis[v] = dis[u] + edge[i].cost;pre[v] = i;if (!vis[v]){vis[v] = true;q.push(v);}}}}if (pre[t] == -1)return false;else return true; } //返回的是最大流，cost存的是最小費(fèi)用 int minCostMaxflow(int s, int t, double &cost) {int flow = 0;cost = 0;while (spfa(s, t)){//cout<<1<<endl; int Min = INF;for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){if (Min > edge[i].cap - edge[i].flow)Min = edge[i].cap - edge[i].flow;}for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){edge[i].flow += Min;edge[i ^ 1].flow -= Min;cost += edge[i].cost * Min;}flow += Min;}return flow; } int main() {int t;scanf("%d", &t);while (t--){int n, m;scanf("%d%d", &n, &m);init(n + 1);for (int i = 1; i <= n; i++){int s, b;scanf("%d%d", &s, &b);int f = s - b;//0是源點(diǎn)，n+1是匯點(diǎn) if (f > 0)///如果人多addedge(0, i, f, 0);else if (f < 0)///如果面包多addedge(i, n + 1, -f, 0);}while (m--){int u, v, f;double w;scanf("%d%d%d%lf", &u, &v, &f, &w);///f是這條路的容量w = -log2(1 - w);///這樣就是正值了if (f > 0)addedge(u, v, 1, 0);///第一個(gè)人經(jīng)過(guò)時(shí)，不破壞if (f - 1>0)addedge(u, v, f - 1, w);///第大于等于2個(gè)人經(jīng)過(guò)時(shí)破壞}double cost = 0;minCostMaxflow(0, n + 1, cost);cost = 1 - pow(2, -cost);printf("%.2lf\n", cost);} }

總結(jié)

以上是生活随笔為你收集整理的Coding Contest HDU - 5988的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。