这个当然 不多余 在跑费用流的时候 我们一般来说就是利用spfa 每次都求出最小代价的增广路然后进行增广。
当然 还有一种算法也可以用于费用流 那就是消圈算法
1. 先在图中跑出最大流
2. 对于图中 如果存在负圈注意很有可能会存在负圈。。
因为 存在一些负边权 和一些反向流量所以存在负圈时 我们可以考虑 跑这条负圈进行增广（说增广理解不太准确了 可以理解为更换匹配关系使付出的代价更小）
这样我们完成了消圈之后 最大流被保证了 且费用为最小的。因为不存在负圈了。
一些博客之中 一直把负圈说成负环 当然这里我认为一个负圈意思是指关系增广路上 这条路径的权值为负。
有负环spfa 不是直接炸了吗 还是我没有理解好我也不太清楚 但是感性的理解往往错不了（可能我说错了 但是自己的理解没错、、）
看这道题很久了 一直没想出来做法 可能被费用流毒害至深吧。。
设 答案为ans 那么显然有 x-y/k=ans 二分出来一个mid 那么显然有 x-y>=mid*k 或者 x-y<=mid*k
挖掘一下题目 调整后不会减少 y是我们调整的代价 从上述式子来看显然y越小越好。 那么则有调整到和原来流量相同的话我们需要付出一些费用但是凭空增加流量的话就比较严重了。你发现无论如何都是增广不了的。。
因为和源点相连就一条边且那条边还不能被调整，这还怎么增广啊坑人。。然后根据二分做题01分数规划不会啊、、
当然 我们 还是可以做下去的 x-y/k=mid 二分出来一个mid 想一下 这个mid 其实mid的必要性是 mid>0且越大越好 如何体现在图中呢？
x-y=mid*k -> x=mid*k+y; ->当前的y 我们是可以表达出来的 x-mid*k=y 这样有点难受毕竟不是不等号 x-y>=mid*k ->mid*k-x+y>=0
把k 抽象成 图上的点后 我们发现这其实就是类似于点权 毕竟是01分数规划我们直接扣上 。有的人可能会问这个mid 不是越大越好么？
的确但是 我们却达不到这个高度我们只能运用已有的 负圈来加流 试想一下 所以对于打不到的mid 肯定是要往下降的。
那下界问题呢 显然 如果mid 过小的话那么存在的问题是 图中还有可能是支配更换关系来做 这样的话 通过消圈原理我们还可以得到最优解。~01分数规划+消圈算法的真谛。
那这道题就被我们做完了。（作为一个初学者我觉得挺难的）
//#include<bits/stdc++.h> #include<iomanip> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<deque> #include<cmath> #include<ctime> #include<cstdlib> #include<stack> #include<algorithm> #include<vector> #include<cctype> #include<utility> #include<set> #include<bitset> #include<map> #define INF 1000000000 #define ll long long #define min(x,y) ((x)>(y)?(y):(x)) #define max(x,y) ((x)>(y)?(x):(y)) #define RI register ll #define db double using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=3000<<1; int n,m,len; db mid; int vis[MAXN]; db dis[MAXN]; int lin[MAXN],ver[MAXN],nex[MAXN],e[MAXN]; inline void add(int x,int y,int z) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; e[len]=z; } inline int dfs(int x) { for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(dis[tn]>dis[x]+e[i]+mid) { dis[tn]=dis[x]+e[i]+mid; if(vis[tn])return 1; vis[tn]=1; if(dfs(tn))return 1; } } vis[x]=0; return 0; } inline int judge()//dfs判负环显然比spfa判负环更快 { for(int i=1;i<=n+2;++i)vis[i]=0,dis[i]=INF; for(int i=1;i<=n+2;++i) { if(dis[i]==INF) { dis[i]=0; if(dfs(i))return 1; } } return 0; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;++i) { int x,y,a,b,c,d; x=read();y=read();a=read(); b=read();c=read();d=read(); if(x==n+1)a=0,b=0,d=0; if(c!=0)add(y,x,a-d); add(x,y,b+d); } db l=0,r=INF*1.0; while(l+0.000001<r) { mid=(l+r)/2; if(judge())l=mid; else r=mid; } printf("%.2lf",l); return 0; }
写的很惨烈 感觉感悟 有很大的缺漏的地方 以后 有机会要复习一下这道题 且和 dalao 交流一下做法。