AC_Dream 1211 Reactor Cooling

 /*
题意:无源无汇,并且每条边的容量有上下界限的网络流问题!既然无源无汇,那么素有的节点都应该满足“入流==出流”!
输出每一条边的流量,使得满足上面的条件。(如果u->v有流量,那么v->u就不会有流量) 思路:如果增加了源点s和汇点t,对于u->v(下限为l, 上限为f) 将这一条边拆成3条,s->v(容量为l), u->v(容量为f-l)
u->t(容量为l)这样就变成了每一个点的流入或者流出的流量至少是b!然后从s->t走一遍最大流,如果所有的附件边都已经
满载,则就是所有s->v的边和u->t的边(或者只判断其中一者就可以),那么就存在答案!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define N 205
#define M 500000
using namespace std; struct EDGE{
int v, cap, tot, nt, b;
EDGE(){};
EDGE(int v, int cap, int nt, int b) : v(v), cap(cap), nt(nt), b(b), tot(cap){}
}; EDGE edge[M];
int n, m;
int first[N];
int pre[N], d[N];
int sz;
int s, t;
int full, fout; void addEdge(int u, int v, int b, int cap){
edge[sz] = (EDGE(v, cap, first[u],b));
first[u] = sz++;
edge[sz] = (EDGE(u, , first[v], ));
first[v] = sz++; edge[sz] = (EDGE(v, b, first[s], ));
first[s] = sz++;
edge[sz] = (EDGE(s, , first[v], ));
first[v] = sz++; edge[sz] = (EDGE(t, b, first[u], ));
full += b;
first[u] = sz++;
edge[sz] = (EDGE(u, , first[t], ));
first[t] = sz++;
} bool bfs(){
queue<int>q;
memset(d, , sizeof(d));
d[s] = ;
q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = first[u]; ~i; i = edge[i].nt){
int v = edge[i].v;
if(!d[v] && edge[i].cap >){
d[v] = d[u] + ;
q.push(v);
}
}
}
if(d[t] == ) return false;
return true;
} int dfs(int u, int totf){
int ff;
if( u == t) return totf;
int flow = ;
for(int i = first[u]; ~i && totf > flow; i = edge[i].nt){
int v = edge[i].v;
int cap = edge[i].cap;
//流入u节点的当前总的流量为totf,可以得到 u->v1, u->v2, u->v3....这些路径上的最大流的和为flow+=f(u->vi)
//f(u->vi)表示u节点沿着vi节点方向的路径上的最大流;如果u->vi+1的容量为wi+1,那么u->vi+1所允许流过的最大
//的流量就是 min(totf - cost, wi+1)了!
if(d[v] == d[u] + && cap > ){
ff = dfs(v, min(totf - flow, cap));
if(ff){
edge[i].cap -= ff;
edge[i^].cap += ff;
flow += ff;
}
else
d[v] = -;//表示v这个点无法在继续增广下去了
}
}
return flow;//返回从u节点向外流出的最大流量!
} bool Dinic(){
while(bfs())
fout += dfs(, INF);//这一块没想到写成while(dfs())会超时.... if( fout != full) return false;
return true;
} int main(){ scanf("%d%d", &n, &m);
memset(first, -, sizeof(first));
sz = ;
fout = full = ;
s = ; t = n+;
int u, v, l, f;
for(int i = ; i <= m; ++i){
scanf("%d%d%d%d", &u, &v, &l, &f);
addEdge(u, v, l, f-l);
}
if(!Dinic()){
printf("NO\n");
return ;
}
printf("YES\n");
for(int i = ; i <= m; ++i){
int j = (i-)*;
printf("%d\n", edge[j].tot - edge[j].cap + edge[j].b);//输出这条边实际流过的流量+下限
} return ;
}
上一篇:css/js(工作中遇到的问题)-3


下一篇:LFS Linux From Scratch 笔记2(经验非教程)BLFS