[学习笔记]费用流-白红宇

[学习笔记]费用流

阅读量：6873 次

发布时间：2019-06-26

本文共 4181 字，大约阅读时间需要 13 分钟。

一些内容在另一篇博客

有的时候要保证最大的情况下，费用尽可能优。

就要用费用流了。

目前所涉及的费用流，都是在最大流的前提下

所以，当题目可以转化成，在保证。。。的情况下，最优化。。。

也许就可以尝试费用流了。

（同样意味着选择，

最小割没有什么最大流的前提，可以没有什么限制地，割掉一些边即可。

但是，每条边必须割掉，不能“割一部分”，对于一些可以剩下的模型就捉襟见肘了。

）

用EK。因为dinic不能保证流出来的是最优代价的。

至于为什么每次贪心选择最优的路径，最后就是最优的，可能的原因是，因为有反边，所以自带反悔自动机功能。贪心没有问题。

可以延伸出来一个结论：

最短路费用流，当前费用是所有能够到达当前总流量的所有费用中最优的一个。

（伪证：

因为贪心成立。还没有听说过哪个贪心不是局部最优解，却是全局最优解的2333

）

例题：

方格取数、晨跑。

拆点费用流即可。

修车，美食节

拆点费用流。

边权设计：

反过来考虑每个人站在某个位置，对后面的人等待时间产生的影响。

第j个阶段，意味着后面还有j个。这样，贡献就只和自己有关系了。

必要的时候动态加边。

倍数关系，这个倍数关系还是质数。

那么，这两个数的质因子一定相差一，差的那个质因子就是这个质数。

所以，把数按照质因子个数奇偶性分成左右两类

左部点右部点自己之间不会有配对。

左部右部点之间，如果成倍数关系，并且一个是另一个质因子个数+1，那么连边流inf，费c1*c2。

左部点和S，连流b费0

右部点和T，连流b费0

这样，每个流就是一个配对。

至于

“在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。”

费用流的特点是，

“可以保证当前的费用永远是当前流量下最优的”

所以，如果当前总费用<0

那么就可以停止了。因为之后，流量更大的话，费用也不可能更高。

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=200*2+5;const int M=200*200+200+200;const int U=31622+20;const int inf=0x3f3f3f3f;int n,m,s,t;struct node{    int nxt,to;    int w;    ll v;}e[2*M];int hd[N],cnt=1;void add(int x,int y,int z,ll c){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].w=z;    e[cnt].v=c;    hd[x]=cnt;}struct po{    int a,b,c;    int cnt;    bool friend operator <(po a,po b){        return a.a
       
        U-10) break;            vis[pri[j]*i]=1;            if(i%pri[j]==0) break;        }    }}int che(int x){    int ret=0;    for(reg i=1;i<=tot&&pri[i]*pri[i]<=x;++i){        if(x%pri[i]==0){            while(x%pri[i]==0) x/=pri[i],++ret;        }        }    if(x!=1) ++ret;    return ret;}ll d[N];int pre[N];int incf[N];queue
        
         q;ll now,flow;bool in[N];bool spfa(){    memset(d,0xcf,sizeof d);    while(!q.empty()) q.pop();    d[s]=0;    q.push(s);    pre[s]=0;incf[s]=inf;    while(!q.empty()){        int x=q.front();q.pop();        in[x]=0;//        cout<<"x "<
         
          <

数字配对

看似费用流。

其实发现，Bob一定选择最大的流量*p

所以，Alice要使得所选择的最大流的最大流量最小。

二分判断即可。

注意，边最大流量不一定是整数。因为可以均摊成小数变得更低。

eps 1e-5即可。

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=103;const int M=1000+3;const int inf=1023333333.00;const double eps=1e-8;int n,m,p,s,t;struct bian{    int x,y,c;}b[M];struct node{    int nxt,to;    double w;}e[2*M];int hd[N],cnt=1;void add(int x,int y,double z){    //cout<<" x y z "<
       
        <<" "<
        
         <<" "<
         
          <
          
           =eps;i=e[i].nxt){        int y=e[i].to;        if(e[i].w&&d[y]==d[x]+1){            double k=dfs(y,min(res,e[i].w));            if(fabs(k)
           
            =eps&&!d[y]){ d[y]=d[x]+1; q[++r]=y; if(y==t) return true; } } } return false;}double dinic(){ double ret=0; double flow=0; while(bfs()){ while((flow=dfs(s,inf))>=eps) ret+=flow; } return ret;}int main(){ scanf("%d%d%d",&n,&m,&p); int x,y,c; s=1,t=n; double R=0.00; for(reg i=1;i<=m;++i){ rd(x);rd(y);rd(c); R=max(R,(double)c); b[i].x=x,b[i].y=y;b[i].c=c; add(x,y,(double)c); add(y,x,0); } int ans=dinic(); printf("%d\n",ans); double L=0.00; R+=2.33; double op=0.00; while(R-L>=eps){ double mid=(L+R)/2; memset(hd,0,sizeof hd);cnt=1; for(reg i=1;i<=m;++i){ add(b[i].x,b[i].y,min((double)b[i].c,mid)); add(b[i].y,b[i].x,0); } double now=dinic(); if(now