洛谷3288 SCOI2014方伯伯运椰子(分数规划+spfa)

纪念博客又一次爆炸了

首先，对于本题中，我们可以发现，保证存在正整数解，就表示一定费用会降低。又因为一旦加大的流量，费用一定会变大，所以总流量一定是不变的

那么我们这时候就需要考虑一个退流的过程

对于原图每一条\(u->v，c>0\)的边，我们在新图中建一条\(v->u，价值是a-d\)

表示退这个流要花费的费用，相当于退流的过程

对于原图任意一条\(u->v\)的边，我们在新图中建一条\(u->v，价值是b+d\)的边，相当于扩流的过程

那么只有成环的时候，才能满足流量平衡这个条件。

正好和消圈定理相类似

所谓消圈定理

就是在某个流 f 中，如果其对应的残余网络没有负圈（剩余流量为 0 的边视为不存在）

那它一定就是当前流量下的最小费用流。

反之亦然。

即「f 是最小费用流等价于其残余网络中没有负圈」。

那根据题目要求的是个比例，那我们一定是只修改最大的那个环就行。

那么我们考虑分数规划一下

二分\(mid <= max(\frac{x-y}{k})\)

\[mid\times k\le x-y
\]

\[mid\times k + (y-x) \le 0
\]

由于在一个环中，k就是这个环的大小，我们可以考虑把每个\(mid\)分配到每个边，也就是转化成了

每条边的权值在原来新图的基础上\(+mid\)，然后\(check\)是否存在负（0）环

这时候直接上\(spfa\)就好，

不过之前的问题转化，还是很有难度啊

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 50010;

const int maxm = 1e6+1e2;

struct Node{

 int u,v,a,b,c,d;

};

Node a[maxn];

int point[maxn],nxt[maxm],to[maxm];

int inque[maxn];

int vis[maxn];

double val[maxm];

queue<int> q;

int cnt,n,m;

double dis[maxn];

int x[maxm],y[maxm];

double w[maxm];

double l=0,r=1e9;

int tmp;

double ans;

bool flag;

int s,t;

void addedge(int x,int y,double w)

{

 //cout<<x<<" "<<y<<" "<<w<<endl;

 nxt[++cnt]=point[x];

 to[cnt]=y;

 val[cnt]=w;

 point[x]=cnt;

}

void spfa(int s)

{

 while (!q.empty()) q.pop();

    for (int i=1;i<=n;i++) dis[i]=1e9;

 memset(inque,0,sizeof(inque));

 memset(vis,0,sizeof(vis));

 dis[s]=0;

 inque[s]=1;

 q.push(s);

 while (!q.empty())

 {

  int x=q.front();

  q.pop();

  vis[x]=0;

  inque[x]++;

  if (inque[x]>=n+1)

  {

   flag=true;

   return;

  }

  //cout<<1<<endl;

  for (int i=point[x];i;i=nxt[i])

  {

   int p =  to[i];

   if (dis[p]>=dis[x]+val[i])

   {

    dis[p]=dis[x]+val[i];

    if (!vis[p])

    {

     q.push(p);

     vis[p]=1;

    }

   }

  }

 }

}

bool check(double mid)

{

 cnt=0;

 flag=false;

 memset(point,0,sizeof(point));

 for (int i=1;i<=tmp;i++)

   addedge(x[i],y[i],w[i]+mid);

    spfa(n-1);

    if (flag) return true;

    else return false;

}

int main()

{

  n=read(),m=read();

  n+=2;

  for (int i=1;i<=m;i++)

  {

     int u=read(),v=read(),a=read(),b=read(),c=read(),d=read();

   ++tmp;

   x[tmp]=u;

   y[tmp]=v;

   w[tmp]=b+d;

   if (c>0)

   {

    ++tmp;

    x[tmp]=v;

    y[tmp]=u;

    w[tmp]=a-d;

   }

  }

 // cout<<check(103)<<endl;

 // return 0;

  while (r-l>1e-3){

   double mid = (l+r)/2;

   if (check(mid)) ans=mid,l=mid;

   else r=mid;

  }

  printf("%.2lf\n",ans);

  return 0;

}

巴特西

洛谷3288 SCOI2014方伯伯运椰子(分数规划+spfa)

最新文章

热门文章