P1940奇怪的游戏Accepted
记录信息
评测状态 Accepted
题目 P1940 奇怪的游戏
递交时间 2016-01-08 21:26:13
代码语言 C++
评测机 ShadowShore
消耗时间 6512 ms
消耗内存 16360 KiB
评测时间 2016-01-08 21:26:22
评测结果
编译成功

foo.cpp: In function 'bool bfs()':
foo.cpp:44:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( register int i = 0 ; i < linker[ now ].size() ; i++ )
^
foo.cpp: In function 'long long int dinic(int, long long int)':
foo.cpp:54:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( register int i = cur[ now ] ; i < linker[ now ].size() ; i++ )
^
foo.cpp: In function 'bool check(long long int)':
foo.cpp:84:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
while( bfs() ) while( temp = dinic( s , inf ) ) ans += temp;
^
测试数据 #0: Accepted, time = 62 ms, mem = 16260 KiB, score = 10
测试数据 #1: Accepted, time = 46 ms, mem = 16268 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 16272 KiB, score = 10
测试数据 #3: Accepted, time = 1656 ms, mem = 16360 KiB, score = 10
测试数据 #4: Accepted, time = 1625 ms, mem = 16356 KiB, score = 10
测试数据 #5: Accepted, time = 953 ms, mem = 16356 KiB, score = 10
测试数据 #6: Accepted, time = 531 ms, mem = 16356 KiB, score = 10
测试数据 #7: Accepted, time = 531 ms, mem = 16360 KiB, score = 10
测试数据 #8: Accepted, time = 468 ms, mem = 16360 KiB, score = 10
测试数据 #9: Accepted, time = 609 ms, mem = 16360 KiB, score = 10
Accepted, time = 6512 ms, mem = 16360 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#define s 0
#define t 1601
#define inf ( 1ll << 50 )

using namespace std;

struct edge
{
int x , y;
long long cap;
edge( int x , int y , long long cap ) : x( x ) , y( y ) , cap( cap ) {}
edge() {}
}e[1000000];

vector < int > linker[1600 + 10];
int dist[1600 + 10] , cur[1600 + 10] , pos;
int n , m , a[40 + 2][40 + 2] , hash[40 + 2][40 + 2] , r;

inline void addedge( int x , int y , long long cap )
{
linker[x].push_back( pos );
e[ pos++ ] = edge( x , y , cap );
linker[y].push_back( pos );
e[ pos++ ] = edge( y , x , 0 );
}

inline bool bfs()
{
queue < int > q;
q.push( s );
memset( cur , 0 , sizeof( cur ) );
memset( dist , -1 , sizeof( dist ) );
int now;
dist[s] = 0;
while( !q.empty() )
{
now = q.front() , q.pop();
for( register int i = 0 ; i < linker[ now ].size() ; i++ )
if( dist[ e[ linker[ now ][i] ].y ] == -1 && e[ linker[ now ][i] ].cap ) q.push( e[ linker[ now ][i] ].y ) , dist[ e[ linker[ now ][i] ].y ] = dist[ now ] + 1;
}
return dist[ t ] > 0;
}

long long dinic( int now , long long low )
{
if( now == t || !low ) return low;
long long temp;
for( register int i = cur[ now ] ; i < linker[ now ].size() ; i++ )
{
cur[ now ] = i;
if( dist[ e[ linker[ now ][i] ].y ] == dist[ now ] + 1 && e[ linker[ now ][i] ].cap && ( temp = dinic( e[ linker[ now ][i] ].y , min( low , e[ linker[ now ][i] ].cap ) ) ) )
{
e[ linker[ now ][i] ].cap -= temp;
e[ linker[ now ][i] ^ 1 ].cap += temp;
return temp;
}
}
return 0;
}

inline bool check( long long x )
{
pos = 0;
for( register int i = s ; i <= t ; i++ )
linker[i].resize( 0 );
long long tot = 0 , ans = 0 , temp;
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= m ; j++ )
if( ( i + j ) & 1 )
{
addedge( s , hash[i][j] , x - a[i][j] ) , tot += x - a[i][j];
if( i != 1 ) addedge( hash[i][j] , hash[i - 1][j] , inf );
if( i != n ) addedge( hash[i][j] , hash[i + 1][j] , inf );
if( j != 1 ) addedge( hash[i][j] , hash[i][j - 1] , inf );
if( j != m ) addedge( hash[i][j] , hash[i][j + 1] , inf );
}
else addedge( hash[i][j] , t , x - a[i][j] );
while( bfs() ) while( temp = dinic( s , inf ) ) ans += temp;
return ans == tot;
}

int main()
{
scanf( "%d" , &r );
while( r-- )
{
scanf( "%d %d" , &n , &m );
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= m ; j++ )
scanf( "%d" , &a[i][j] );
int num = 0;
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= m ; j++ )
hash[i][j] = ++num;
int mx = 0 , cnt1 = 0 , cnt2 = 0;
long long ans1 = 0 , ans2 = 0;
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= m ; j++ )
mx = max( mx , a[i][j] );
for( register int i = 1 ; i <= n ; i++ )
for( register int j = 1 ; j <= m ; j++ )
if( ( i + j ) & 1 ) ans1 += a[i][j] , cnt1++;
else ans2 += a[i][j] , cnt2++;
if( cnt1 != cnt2 )
{
long long temp = ( ans1 - ans2 ) / ( cnt1 - cnt2 );
if( temp >= mx && check( temp ) ) cout << temp * cnt1 - ans1 << endl;
else puts( "-1" );
}
else
{
if( ans1 != ans2 )
{
puts( "-1" );
continue;
}
long long l = mx , r = inf , mid , ans = -1;
while( l <= r )
{
mid = ( l + r ) >> 1;
if( check( mid ) ) ans = mid , r = mid - 1;
else l = mid + 1;
}
if( ans != -1 ) cout << ans * cnt1 - ans1 << endl;
else puts( "-1" );
}
}
return 0;
}

http://accepted.com.cn/vijos1940/