集团公司手机站网站,自建网站平台要多少钱,怎样创建自己的公众号,网站更换域名多少钱正题
题目链接:https://www.luogu.com.cn/problem/P3288 题目大意
给出nnn个点mmm条边的一张图#xff0c;没条边iii流量为cic_ici#xff0c;费用是did_idi#xff0c;然后缩小一个流量费用是aia_iai#xff0c;增加一个流量费用是bib_ibi。
要求改动图之后最大…正题
题目链接:https://www.luogu.com.cn/problem/P3288 题目大意
给出nnn个点mmm条边的一张图没条边iii流量为cic_ici费用是did_idi然后缩小一个流量费用是aia_iai增加一个流量费用是bib_ibi。
要求改动图之后最大流不减少
假设减少的费用是ΔX\Delta XΔX改动次数是kkk求最大化ΔXk\frac{\Delta X}{k}kΔX
1≤n≤5000,1≤m≤30001\leq n\leq 5000,1\leq m\leq 30001≤n≤5000,1≤m≤3000 解题思路
因为最大流不减少那么显然因为初始边最大流也不能增加所以每次肯定是选一条回路增流或者退流这样就是把增流的丢到环上退流的去。
然后对于一条边增流的费用就是ai−dia_i-d_iai−di退流的费用是bidib_id_ibidi
然后最大化的那个显然是一个分数规划就直接二分答案然后边权加上答案看有没有负环就好了。 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N5e310;
struct node{int to,next;double w;
}a[N1];
int n,m,tot,ls[N],cnt[N];
double f[N];bool v[N];queueint q;
void addl(int x,int y,double w){a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;return;
}
bool SPFA(double w){for(int i1;in2;i)f[i]1e100,cnt[i]0;q.push(n1);f[n1]cnt[n1]0;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wwf[y]){f[y]f[x]a[i].ww;cnt[y]cnt[x]1;if(cnt[y]na[i].w0)return 1;if(!v[y])q.push(y),v[y]1;}}}return 0;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;double A,B,C,D;scanf(%d%d,x,y);scanf(%lf%lf%lf%lf,A,B,C,D);
// if(xn1)A0,B0,D0;if(C0)addl(y,x,A-D);addl(x,y,BD);}double l0,r1e8;for(int i1;i100;i){double mid(lr)/2.0;if(SPFA(mid))lmid; else rmid;}printf(%.2lf\n,(lr)/2.0);return 0;
}
