sgu 194 上下界网络流可行流判定+输出可行流

 #include <cstdio>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
#define oo 0x3f3f3f3f
#define N 210
#define M 100010 struct Dinic {
int n, src, dst;
int head[N], dest[M], flow[M], eid[M], next[M], etot;
int cur[N], dep[N], qu[N], bg, ed; void init( int n, int src, int dst ) {
this->n = n;
this->src = src;
this->dst = dst;
etot = ;
memset( head, -, sizeof(head) );
}
void adde( int id, int u, int v, int f ) {
next[etot]=head[u], flow[etot]=f, dest[etot]=v, eid[etot]=id; head[u]=etot++;
next[etot]=head[v], flow[etot]=, dest[etot]=u, eid[etot]=-; head[v]=etot++;
}
bool bfs() {
memset( dep, , sizeof(dep) );
qu[bg=ed=] = src;
dep[src] = ;
while( bg<=ed ) {
int u=qu[bg++];
for( int t=head[u]; ~t; t=next[t] ) {
int v=dest[t], f=flow[t];
if( f && !dep[v] ) {
dep[v] = dep[u]+;
qu[++ed] = v;
}
}
}
return dep[dst];
}
int dfs( int u, int a ) {
if( u==dst || a== ) return a;
int remain=a, past=, na;
for( int &t=cur[u]; ~t; t=next[t] ) {
int v=dest[t], &f=flow[t], &vf=flow[t^];
if( f && dep[v]==dep[u]+ && (na=dfs(v,min(remain,f))) ) {
f -= na;
vf += na;
remain -= na;
past += na;
if( !remain ) break;
}
}
return past;
}
int maxflow() {
int f = ;
while( bfs() ) {
for( int u=; u<=n; u++ ) cur[u]=head[u];
f += dfs(src,oo);
}
return f;
}
void print( int *ans ) {
for( int e=; e<etot; e++ )
if( eid[e]!=- ) ans[eid[e]]+=flow[e^];
}
}D;
struct Bottop {
int n;
int head[N], dest[M], bot[M], top[M], next[M], eid[M], etot;
int si[N], so[N], sum; void init( int n ) {
this->n = n;
memset( head, -, sizeof(head) );
memset( si, , sizeof(si) );
memset( so, , sizeof(so) );
etot = ;
}
void adde( int id, int u, int v, int b, int t ) {
eid[etot]=id, next[etot]=head[u], bot[etot]=b, top[etot]=t, dest[etot]=v;
head[u]=etot++;
}
void build( int *ans ) {
int src=n+, dst=n+;
D.init( dst, src, dst );
for( int u=; u<=n; u++ )
for( int t=head[u]; ~t; t=next[t] ) {
int v=dest[t];
ans[eid[t]] += bot[t];
si[v] += bot[t];
so[u] += bot[t];
D.adde( eid[t], u, v, top[t]-bot[t] );
}
for( int u=; u<=n; u++ ) {
if( so[u]>si[u] )
D.adde( -, u, dst, so[u]-si[u] );
else if( si[u]>so[u] ) {
D.adde( -, src, u, si[u]-so[u] );
sum += si[u]-so[u];
}
}
}
bool ok() { return D.maxflow()==sum; }
}B; int n, m;
int ans[M]; int main() {
scanf( "%d%d", &n, &m );
B.init(n);
for( int i=,u,v,b,t; i<=m; i++ ) {
scanf( "%d%d%d%d", &u, &v, &b, &t );
B.adde( i, u, v, b, t );
}
B.build(ans);
bool ok = B.ok();
printf( "%s\n", ok ? "YES" : "NO" );
if( ok ) {
D.print( ans );
for( int i=; i<=m; i++ )
printf( "%d\n", ans[i] );
}
}
上一篇:CSS垂直居中对齐


下一篇:Linux下l2tp客户端xl2tpd的安装配置