最大流|LOJ6004 「网络流 24 题 - 5」圆桌聚餐最大流最大流|网络流24题

大家都很强，可与之共勉。题意：
??假设有来自 n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri ?? 。会议餐厅共有 m 张餐桌，每张餐桌可容纳 ci 个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。
??问是否存在方案，若存在输出一种方案。
题解：
??最大流满流判是否有解。然后输出方案判哪些边被流满流。
??建边方式：

我们虚拟一个原点 S 和汇点 T 。
然后把单位认为是 X 集合，餐桌认为是 Y 集合。
S 向 X 集合里面的所有元素连一条容量为其代表人数的弧， Y 集合的每一个元素向 T 连一条容量为其容纳人数的弧。
X 集合中的每一个元素向 Y 集合中的每一个元素连一条容量为 1 的弧（我认为不要求输出方案的话是可以虚拟节点的连 |X|+|Y| 条边，输出方案也可以，只是麻烦一点）。

【最大流|LOJ6004 「网络流 24 题 - 5」圆桌聚餐最大流】??然后最大流，如果满流就存在解

# include # define N 5010class Network{ private : struct edge{ int to, w, nxt ; edge ( ) {} edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) {} } g [60010 << 1] ; int head [N], cur [N], ecnt ; int S, T , dep [N] ; inline int dfs ( int u, int a ){ if ( u == T || ! a )return a ; int flow = 0, v, f ; for ( int& i = cur [u] ; i ; i = g [i].nxt ){ v = g [i].to ; if ( dep [v] == dep [u] + 1 ){ f = dfs ( v, std :: min ( g [i].w, a - flow ) ) ; g [i].w -= f, g [i ^ 1].w += f ; flow += f ; if ( a == flow )return a ; } } if ( ! flow )dep [u] = -1 ; return flow ; }inline bool bfs ( int S, int T ){ static std :: queue < int > q ; memset ( dep, 0, sizeof ( int ) * ( T + 1 ) ) ; dep [S] = 1 ; q.push ( S ) ; while ( ! q.empty ( ) ){ int u = q.front ( ) ; q.pop ( ) ; for ( int i = head [u] ; i ; i = g [i].nxt ){ int& v = g [i].to ; if ( g [i].w &&! dep [v] ){ dep [v] = dep [u] + 1 ; q.push ( v ) ; } } } return dep [T] ; } public : Network ( ){ecnt = 1 ; }inline void add_edge ( int u, int v, int w ){ g [++ ecnt] = edge ( v, w, head [u] ) ; head [u] = ecnt ; g [++ ecnt] = edge ( u, 0, head [v] ) ; head [v] = ecnt ; }inline void clear ( ){ ecnt = 1 ; memset ( head, 0, sizeof head ) ; } inline int dinic ( int S, int T ){ this -> S = S, this -> T = T ; static int rt = 0 ; // static ; while ( bfs ( S, T ) ){ memcpy ( cur, head, sizeof ( int ) * ( T + 1 ) ) ; rt += dfs ( S, 0x3f3f3f3f ) ; } return rt ; }void display ( int n, int m, int sum, int S, int T ){ if ( dinic ( S, T ) == sum ){ puts ( "1" ) ; }else{ puts ( "0" ) ; return ; } for ( int i = 1 ; i <= n ; ++ i ){ for ( int j = head [i] ; j ; j = g [j].nxt ) if ( g [j].w == 0 && g [j].to <= m + n ){ printf ( "%d ", g [j].to - n ) ; } puts ( "" ) ; } } } Lazer ; int main ( ){ int n, m ; int sum ( 0 ) ; scanf ( "%d%d", & n, & m ) ; const int S = n + m + 1, T = n + m + 2 ; for ( int i = 1 ; i <= n ; ++ i ){ static int x ; scanf ( "%d", & x ) ; sum += x ; Lazer.add_edge ( S, i, x ) ; } for ( int i = 1 ; i <= m ; ++ i ){ static int x ; scanf ( "%d", & x ) ; Lazer.add_edge ( i + n, T, x ) ; }for ( int i = 1 ; i <= n ; ++ i )//Lazer.add_edge ( i, X, 0x3f3f3f3f ) ; for ( int j = 1 ; j <= m ; ++ j ){//Lazer.add_edge ( X, i + n, 0x3f3f3f3f ) ; Lazer.add_edge ( i, j + n, 1 ) ; } Lazer.display ( n, m, sum, S, T ) ; return 0 ; }