自己电脑做服务器搭建网站有域名,常见的网址有哪些,电商网站的建设背景图片,app小程序Coding Contest HDU - 5988
题意#xff1a;
有n个点#xff0c;m个边#xff0c;每个点有人数和食物数#xff0c;每个人都要吃一份食物#xff0c;如果该点的食物不够#xff0c;他们就要去其他点#xff0c;每个边最多只能走c次#xff0c;每次有人走一条路#…Coding Contest HDU - 5988
题意
有n个点m个边每个点有人数和食物数每个人都要吃一份食物如果该点的食物不够他们就要去其他点每个边最多只能走c次每次有人走一条路这条路就有p的概率坏掉。第一个人通过时不会坏掉。求最小破坏的电线的概率
题解
不难看出是一个网络流但是不知道该怎么建边(这也是网络流最难的部分) 参考题解 每条边都有走的次数(当作流量)每个边走一次发生破坏的概率为p(流量1费用p),我们开始建立费用流图。根据题意每个边坏掉概率如果走多个边那概率应该相乘但是费用流往往是累加的如何将相乘转成累加我们可以通过对每个概率取log当成费用在log下所有都是相加减。 但是题目的概率都是小于1的如果取log都是负数费用为负这跑出来有问题跑出来的费用会朝着更小走。如何解决那么取个负数呢还是不行因为取负后最小的变成最大的跑出来就成最大费用了 此时我们应该这样考虑题目要求求最小概率也就是1-最大概率因此我们把每条边的概率赋值为1-p然后取反取log这样跑正好得到的是最小费用取出来之后再用1减去就好了 add(u,v,f,-log2(1-p)),f为容量p为概率从u到v的边 其他如何建边 建立源点s汇点t对于SB人多从源点连一条流量为S[i]-B[i]费用为0对于sb粮食多)的从该点向t连个边费用为B[i]-S[i] 题目还说第一次踩不会坏所以从原有的边取一条出来流量为1费用为0
代码
#includecstdio
#includealgorithm
#includecstring
#includeiostream
#includecmath
#includequeue
#includestring
#includefunctional
typedef long long LL;
using namespace std;
#define MAXN 110
#define MAXM 25000
#define ll l,mid,now1
#define rr mid1,r,now1|1
#define lson l1,mid,l2,r2,now1
#define rson mid1,r1,l2,r2,now1|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;//节点总个数节点编号从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)
{queueintq;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()){//cout1endl; 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].costeps){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存的是最小费用
int minCostMaxflow(int s, int t, double cost)
{int flow 0;cost 0;while (spfa(s, t)){//cout1endl; 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是源点n1是汇点 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);///第一个人经过时不破坏if (f - 10)addedge(u, v, f - 1, w);///第大于等于2个人经过时破坏}double cost 0;minCostMaxflow(0, n 1, cost);cost 1 - pow(2, -cost);printf(%.2lf\n, cost);}
}