ZOJ 3229 Shoot the Bullet (有上下界的最大流)

ZOJ 3229 Shoot the Bullet 

前几天看了有上下界的各种流，使劲看啊使劲看，终于有点眉目，然后就刷这个题去了。。然后就被虐了= =

之前看书说是求最大流的时候需要二分下界看是否有可行流，但是，我想来想去，这尼玛坑爹啊，怎么都会超时的，但是试了各种二分，dinic，sap都用了，就是超时，感觉一定有什么不对劲，放那里，过两天再看。。

今天小媛赐予我《新编实用算法与程序设计》，俗称蓝书，看了看二分图部分后，就顺便看了看网络流的部分，里面有讲这个，我仔细看了看，终于理解了求可行流时候为什么要那样构图，而且发现其实不用二分下界，只需要删掉T->S的弧，然后求个S,T的最大流就行了。。因为下界（必满，已经在求可行流时候满足了）没有包含在残量网络里，所以直接扩流就行了  = =。。。

对于本题，因为有些奇怪的单词，可能读题比较困难，n天给m个mm拍照，每个mm有拍照数量下限，每天有拍照数量的上界，每天拍照某个mm也有数量限制，求这n天能拍到的最多的mm数，和每天拍的数量。建图很弱啦。。。。代码木有注释，。。。凑活着看吧。。。=  =

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
const int MAXN = 365+1000+4;
const int inf = 99999999;

class Arc{
public:
int to,w;
int l,r;
Arc *next,*anti;
Arc *add( int tt,int ll,int rr,Arc *&b ){
to = tt; l = ll; r = rr;
w = rr-ll;next = b;b = this; return this;
}
};

int d[ MAXN ],S,T,bound,countt,in[ MAXN ],out[ MAXN ];
Arc a[ MAXN *80 ],*biao[ MAXN ];

void init( int n ){
bound = n;S = n - 2;T = n - 1;
for( int i = 0; i < n; i++ )
biao[i] = NULL;
memset( in, 0, sizeof(in) );
memset( out, 0, sizeof(out) );
countt = 0;
}

void add( int from,int to, int l,int r ){
Arc *p1 = a[ countt++ ].add( to, l, r, biao[from] );
Arc *p2 = a[ countt++ ].add( from, 0, 0, biao[to] );
p1->anti = p2;
p2->anti = p1;
}

int bfs( void ){
queue<int> q;
fill( d,d+MAXN,-1 );
d[ S ] = 0;
q.push( S );
while( !q.empty() ){
int u = q.front();q.pop();
for( Arc *p=biao[u]; p!=NULL; p=p->next )
if( d[ p->to ] == -1 && p->w > 0 )
d[ p->to ] = d[u] + 1,q.push( p->to );
}
return d[ T ] != -1;
}

int dinic( int u ,int sum){
int f,o = sum;
if( u == T ) return sum;
for( Arc *p = biao[u]; p!=NULL && sum; p=p->next )
if( d[p->to] == d[u] + 1 && p->w > 0){
f = dinic( p->to, min( p->w,sum) );
p->w -= f;
p->anti->w += f;
sum -= f;
}
return o - sum;
}

int max_flow1( void ){
int total = 0;
while( bfs() )
total += dinic( S, 2100000000 );
return total;
}

int max_flow(){
int i,now_flow,total,min_dist;
Arc *ge[MAXN],*di[MAXN],*path[MAXN];
int dist[MAXN],countdist[MAXN],his[MAXN],pre[MAXN],n=bound;
Arc *p,*locate;
bool flag;
memset( dist,0,sizeof(dist) );
memset( countdist,0,sizeof( countdist) );
countdist[0] = n;
for( i = 0; i < n ; i++ ) di[i] = ge[i] = biao[i];
for( total = 0, now_flow = inf,i = S; dist[i] < n; ){
his[i] = now_flow;
for( flag = false,p=di[i]; p!=NULL; p= p->next){
if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){
now_flow = min( now_flow,p->w );
pre[ p->to ] = i;
path[ p->to ] = p;
di[i] = p;
i = p->to;
if( i == T ){
for( total += now_flow; i != S; i = pre[i] )
path[i]->w -= now_flow, path[i]->anti->w += now_flow;
now_flow = inf;
}
flag = true;
break;
}
}
if( !flag ){
for( min_dist = n-1,p=ge[i];p!= NULL;p=p->next )
if( p->w > 0 && dist[p->to] < min_dist )
min_dist = dist[p->to],locate = p;
di[i] = locate;
if( !(--countdist[ dist[i] ] ) ) break;
countdist[ dist[i] = min_dist+1 ] ++;
if( i != S )
i = pre[i],now_flow = his[i];

}
}
return total;
}

void construct( void ){
for( int i = 0; i < bound - 2; i++ )
for( Arc *p=biao[i]; p!=NULL; p = p->next ){
in[ p->to ] += p->l;
out[ i ] += p->l;
}
for( int i = 0; i < bound - 2; i++ ){
add( S, i, 0, in[i]  );
add( i, T, 0, out[i] );
}
}

bool full( void ){
for( Arc *p = biao[S]; p != NULL; p = p->next )
if( p->w > 0 ) return false;
return true;
}

int main(void){
int n,m,from,to;
int i,j,c,d,r,l;
while( scanf("%d%d",&n,&m) != EOF ){
init(n+m+4);
for( i = 0; i < m; i++ ){
scanf("%d",&j);
add( n+i, n+m+1, j, inf );
}
queue<int> q;
for( i = 0; i < n; i++ ){
scanf("%d%d",&c,&d);
add( n+m, i, 0, d );
while( c-- ){
scanf("%d%d%d",&j,&r,&l);
q.push( countt );
add( i, n+j, r, l );
}
}
j = countt;
add( n+m+1, n+m, 0, inf );
construct();
max_flow();

if( !full() ){
puts("-1\n");continue;
}
a[j].w = a[j+1].w = 0;
S = n+m;T = S+1;
max_flow1();
int total = 0;
for( Arc *p = biao[S]; p != NULL; p = p->next )
if( p->to >= 0 && p->to < n ) {
total += p->r - p->w;
}
printf("%d\n",total);
while( !q.empty() ){
int u = q.front();q.pop();
printf("%d\n",a[u].r - a[u].w );
}
printf("\n");
}
return 0;
}

一个max_flow是sap，一个max_flow1是dinic，都能过，这个题就可以作为我的模板了。。。
网络流以后应该向建图方面发展了，知识性的东西在以后做题过程中巩固吧。。