[ZOJ3362 Beer Problem]【最大费用流】【Not 最大费用最大流】【流中无向边与有向边的详细YY】

【题目大意】
1是源点，其它的n-1个点都可以流出。每滴水所得的费用w[i]。
然后给出一些无向边，流走过这些边，每滴水要消耗费用，并且只能有c滴水通过这条路。
就是比如给定(x,y)，容量为c。
从x到y流过f1滴水，从y到x流过f2滴水，那么f1+f2<=c。
求怎样得到最大利润。
【算法分析】
把那n-1个点汇到一个超级汇中作最大费用最大流就行了。
至于无向边的问题，我们只要加两条有向边就行了。
大牛可以无视下面这个入门问题。。。= =
那么我们现在看一下为啥加两条有向边是对的。
假设一条无向边(x,y)，他允许通过流量为c。
我们现在搞成两个有向边。
1、x->y，容量为c
2、y->x，容量为c
我们再假设最终完成一个流以后，x->y的流为f1，y->x的流为f2，由于对称，不妨设f1>=f2。
那么本质可以变成x->y的流为f1-f2，y->x的流为0。
我们这样考虑：
本来有f2的流S->y->x->T。
同时有f1的流S->x->y->T，并有f1>=f2。
那么现在S->y上的流有f2这么多被分到y->x上了，我们现在把他扯回来。存在y结点上。
于是y点存的水e(y)=f2
再把S->x->y的流扯回来，存在x结点上。
于是x点存的水e(x)=f1
然后现在观察发现。
x->T部分和原来相比，缺了f2，需要补充f2的流来满足流量守恒。
y->T部分和原来相比，缺了f1，需要补充f1的流。
然后我们把e(x)中f1的流分配给x->T这条路，那么分完以后e(x)=f1-f2。
然后再把e(y)中f2的流分配给y->T这条路，那么分完以后e(y)=0。并且y->T这条路还缺少f1-f2的流补充。
于是最后，把e(x)中的流，通过x->y，补给到y->T这条路上。
就完成了这个转化。
所以，凡是x->y中有流，且y->x中也有流的结果，我们都可以转化为只有一条有流的结果。
并且边上的流都小于等于原来的。
这样，就证明了这样加边最后必然与合法解所对应，如果要输出方案的话，把所有这种对应边的流量相互抵消以后输出，就可以得到满足条件的解。
/
/
/
/
/
但是，我们只是证明了无费用的情况。
如果按照这样转化总费用是会变化的！
对于(x,y)这条边而言，一开始取了f1+f2个单位的费用，而转化以后只取了f1-f2的费用。
我们现在再分情况仔细YY一下：
1、求最大费用流，如果该无向边权值>0，显然无法求。。。就像有正权环的最长路一样。
但是如果该无向边的权值<0，显然按照上面的推导，f1+f2>f1-f2。（假设f1>=f2 && f1,f2>0）。
我们的费用流不会这么笨去取那个更差的解。
2、求最小费用流，基本上面的词取反义词就是了T_T。

还有，本题求的是最大费用流，流不一定要最大，只要流满足限制即可。我们找增广路如果找到增广费用小于等于0，就可以马上停止了。
如果是最大费用最大流，找增广路的话，要找到找不到为止。
【其它】1Y。呃~希望有同样困惑的童鞋们看完可以清楚一点。
【CODE】
#include #include #include #include #include using namespace std;
const int N=105;
const int E=40000;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];
int m,n,S,T,e,cost;
int d[N],v[N],L[N];

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w= w; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
for (int i=1;i<=n+1;i++) ls[i]=NULL;
e=-1; S=1; T=n+1;
for (int w,i=2;i<=n;i++){
cin >> w;
addedge(i,T,INF,w);
}
for (int x,y,c,w,i=1;i<=m;i++){
cin >> x >> y >> c >> w;
addedge(x,y,c,-w);
addedge(y,x,c,-w);
}
}

bool spfa(){
for (int i=S;i<=T;i++){
d[i]=-INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
int head=0,tail=1;
while (head!=tail){
head=(head+1)%N;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
L[tail=(tail+1)%N]=t->y;
}
}
v[L[head]]=0;
}
return d[T]>0;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
nf=min(nf,fa[i]->c);
cost+=nf*d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void MCMF(){
cost=0;
while (spfa()) change();
cout << cost << 'n';
}

int main(){
ios::sync_with_stdio(false);
while (cin >> n >> m){
init();
MCMF();
}
}