本来想写道水题....结果调了这么久！就是一个 define 里面少加了个括号 ！
二分图最大点权独立集...黑白染色一下 , 然后建图 :
S -> black_node , white_node -> T , 流量都为点权 . 然后 black_node -> white_node ( 两点有公共边 ) , 流量为 +oo , 然后 answer = ∑ w( i ) ( i ∈ V ) - maxflow
-------------------------------------------------------------------------------------------------
#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 id( x , y ) ( ( x ) * n + y + 1 )
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 1000;
struct edge {
int to , cap;
edge *next , *rev;
} E[ maxn << 3 ] , *pt = E , *head[ maxn ];
inline void add_edge( int u , int v , int w ) {
pt -> to = v;
pt -> cap = w;
pt -> next = head[ u ];
head[ u ] = pt++;
pt -> to = u;
pt -> cap = 0;
pt -> next = head[ v ];
head[ v ] = pt++;
head[ u ] -> rev = head[ v ];
head[ v ] -> rev = head[ u ];
}
int h[ maxn ] , cnt[ maxn ] , S , T , N;
edge *cur[ maxn ] , *p[ maxn ];
int maxFlow() {
clr( h , 0 ) , clr( cnt , 0 );
cnt[ 0 ] = N;
rep( i , N ) cur[ i ] = head[ i ];
int flow = 0 , A = inf;
edge* e;
for( int x = S ; h[ S ] < N ; ) {
for( e = cur[ x ] ; e ; e = e -> next )
if( h[ e -> to ] + 1 == h[ x ] && e -> cap ) break;
if( e ) {
A = min( A , e -> cap );
p[ e -> to ] = cur[ x ] = e;
if( ( x = e -> to ) == 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;
}
int main(){
freopen( "test.in" , "r" , stdin );
clr( head , 0 );
int ans = 0 , n;
cin >> n;
S = 0 , T = n * n + 1 , N = T + 1;
rep( i , n )
rep( j , n ) {
int w;
scanf( "%d" , &w );
ans += w;
if( ( i + j ) & 1 ) {
add_edge( S , id( i , j ) , w );
if( i ) add_edge( id( i , j ) , id( i - 1 , j ) , inf );
if( j ) add_edge( id( i , j ) , id( i , j - 1 ) , inf );
if( i + 1 < n ) add_edge( id( i , j ) , id( i + 1 , j ) , inf );
if( j + 1 < n ) add_edge( id( i , j ) , id( i , j + 1 ) , inf );
} else
add_edge( id( i , j ) , T , w );
}
cout << ans - maxFlow() << "\n";
return 0;
}
-------------------------------------------------------------------------------------------------
1475: 方格取数
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 616 Solved: 323
[Submit][Status][Discuss]
Description
在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。
Input
第一行一个数n；（n<=30） 接下来n行每行n个数描述一个方阵
Output
仅一个数，即最大和
Sample Input
2
1 2
3 5
1 2
3 5
Sample Output
6