![BZOJ 1305: [CQOI2009]dance跳舞( 最大流 )](/default/index/img?u=aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmFXMWhaMlZ6TUM1amJtSnNiMmR6TG1OdmJTOWliRzluTWpBeE5TODNNak00T1RZdk1qQXhOVEEzTHpBNE1qRTFOVEk1T0RjM05qVXlOeTV3Ym1jPS5qcGc= "BZOJ 1305: [CQOI2009]dance跳舞( 最大流 )")
云神代码很短...0 ms过的...看了代码 , 大概是贪心... orz 我不会证
数据这么小乱搞就可以了吧... ←_←
这道题网络流还是可以写的...
既然限制了最多只能和 k 个不喜欢的人dance , 那么就把每个人拆成 a , b 两个点 . 限制完了之后 , 因为 n <= 50 , 我们可以直接从从小到大枚举 , 一个一个增广 .
具体建图 :
boy_a( i ) -> boy_b( i ) ( cap : k ) , girl_b( i ) -> girl_a( i ) ( cap : k ) ( 1 <= i <= n )
对于两个人 boy( i ) , girl( j ) :
boy( i ) and girl( j ) are friends : boy_a( i ) -> girl_a( j ) ( 1 )
boy( i ) and girl( j ) aren't friends : boy_b( i ) -> girl_b( j ) ( 1 )
然后每次给 S -> boy_a( i ) , girl_a( i ) -> T ( 1 <= i <= n ) 加一条 1 的弧 , 跑一下看增加的流量是否为 n , 假如是就继续并将答案 + 1 , 不是就结束
-------------------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( x , c ) memset( x , c , sizeof( x ) )
#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )
using namespace std;
const int maxn = 200 + 10;
const int maxm = 20000;
const int inf = 1e8;
struct edge {
int to , cap;
edge *next , *rev;
} *pt , *head[ maxn ] , E[ maxm ];
inline void add( int u , int v , int d ) {
pt -> to = v;
pt -> cap = d;
pt -> next = head[ u ];
head[ u ] = pt++;
}
inline void add_edge( int u , int v , int d ) {
add( u , v , d );
add( v , u , 0 );
head[ u ] -> rev = head[ v ];
head[ v ] -> rev = head[ u ];
}
void edge_init() {
pt = E;
clr( head , 0 );
}
int h[ maxn ] , cnt[ maxn ];
edge *p[ maxn ] , *cur[ maxn ];
int N , S , T;
int maxFlow() {
clr( cnt , 0 ) , cnt[ 0 ] = N;
clr( h , 0 );
rep( i , N ) cur[ i ] = head[ i ];
int A = inf , x = S , flow = 0;
edge* e;
while( h[ S ] < N ) {
for( e = cur[ x ] ; e ; e = e -> next )
if( e -> cap && h[ x ] == h[ e -> to ] + 1 ) break;
if( e ) {
p[ e -> to ] = cur[ x ] = e;
A = min( A , e -> cap );
x = e -> to;
if( x == T ) {
for( ; x != S ; x = p[ x ] -> rev -> to ) {
p[ x ] -> cap -= A;
p[ x ] -> rev -> cap += A;
}
flow += A;
A = inf;
}
} else {
if( ! --cnt[ h[ x ] ] ) break;
h[ x ] = N;
for( e = head[ x ] ; e ; e = e -> next )
if( e -> cap && h[ e -> to ] + 1 < h[ x ] ) {
h[ x ] = h[ e -> to ] + 1;
cur[ x ] = e;
}
++cnt[ h[ x ] ];
if( x != S ) x = p[ x ] -> rev -> to;
}
}
return flow;
}
#define boy_a( i ) ( i )
#define girl_a( i ) ( i + ( n << 1 ) )
#define boy_b( i ) ( i + n )
#define girl_b( i ) ( i + n * 3 )
int main() {
freopen( "test.in" , "r" , stdin );
freopen( "test.out" , "w" , stdout );
edge_init();
int n , k;
char c;
cin >> n >> k;
S = 0 , T = 4 * n + 1 , N = T + 1;
Rep( i , n ) {
add_edge( boy_a( i ) , boy_b( i ) , k );
add_edge( girl_b( i ) , girl_a( i ) , k );
}
Rep( i , n )
Rep( j , n ) {
scanf( " %c" , &c );
if( c == 'Y' )
add_edge( boy_a( i ) , girl_a( j ) , 1 );
else
add_edge( boy_b( i ) , girl_b( j ) , 1 );
}
int ans = 0;
for( ; ; ) {
Rep( i , n ) {
add_edge( S , boy_a( i ) , 1 );
add_edge( girl_a( i ) , T , 1 );
}
if( maxFlow() == n ) ans++;
else break;
}
cout << ans << "\n";
return 0;
}
-------------------------------------------------------------------------------------------------
1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 1863 Solved: 793
[Submit][Status][Discuss]
Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。
Output
Sample Input
3 0
YYY
YYY
YYY
Sample Output
3
HINT
Source