以前刚开始看网络流的时候,下载过一个文档,《网络流建模汇总 by Edelweiss》,里面第一个模型就是这个题,当时看了好长时间,没看懂= =b,这两天重新看过之后,思路清晰了许多。网络流难的不是dinic,sap呀什么的,是建图,搞死人呢。。。
经过一番搜题解之后,我发现最详细的解释出自这里,凑活着看吧,上面的文档中也有(不过我打印出来是黑白的,图示不清)。
我就不多说了(= =b,是不是很不厚道)。以下代码是我1Y的,用class封装的dinic,现在用着已经很爽了,用virtual judge交的时候还跑了个0ms。
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> const int maxn = 110; const int maxm = 1010; const int inf = 2100000000; using namespace std; class Arc{ public: int to,w; Arc *next,*anti; Arc *ass( int tt,int ww,Arc* &b ){ to = tt;w = ww;next = b;b = this;return this; } }; class Network{ public: Arc a[ 5000 ],*biao[ maxn ]; int countt,total,d[maxn],S,T; Network(void) {} Network( int n ) {init(n) ;} void init( int n ){ countt = 0; for( int i = 0; i < n; i++ ) biao[i] = NULL; S = n - 2;T = n - 1; } void add( int from,int to,int w ){ Arc *p1 = a[countt++].ass( to,w ,biao[from]); Arc *p2 = a[countt++].ass( from,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; if( u == T ) return sum; o = sum; for(Arc*p=biao[u];p!=NULL&∑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 maxflow( int s, int t ){ S = s;T = t; int total = 0; while( bfs() ) total += dinic(S,inf ); return total; } }; int N,M,A,B; int has[ maxm ]; int buy[ maxn ]; int main(void){ int i,j,k; while( scanf("%d%d",&M,&N) != EOF ){ Network net( N + 3 ); vector<int> V[maxm]; for( i = 1; i <= M; i++ ) scanf("%d",&has[i] ); for( i = 1; i <= N; i++ ){ scanf("%d",&A); while( A-- ){ scanf("%d",&j); V[j].push_back(i); } scanf("%d",&buy[i]); } for( i = 1; i <= M; i++ ){ if( V[i].size() == 0 ) continue; net.add( net.S, V[i][0], has[i] ); for( j = 1; j < V[i].size(); j++ ) net.add( V[i][j-1], V[i][j], inf ); } for( i = 1; i <= N; i++ ) net.add( i, net.T, buy[i]); printf("%d\n", net.maxflow(net.S,net.T) ); } return 0; }
我已经快被搞崩溃了,每个人说的都不一样 😥
如果A打开了K个猪圈,那么这K个猪圈的猪可能被他们的下一个客户访问到