「BZOJ2756」[SCOI2012] 奇怪的游戏

2015年1月3日9,1396

Description

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。

Input

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。

Output

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。

Sample Input

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

2
-1

HINT

「数据范围」
对于30%的数据，保证 T<=10，1<=N,M<=8
对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

题解

对棋盘进行黑白染色
设黑格个数为num1 数值和为sum1
设白格个数为num1 数值和为sum1

设最后都变为x
则
num1 * x – sum1 = num2 * x – sum2
x = (sum1 – sum2) / (num1 – num2)
当num1 ≠ num2时可以解出 x 再用网络流check即可

对于num1 = num2时可以发现对于一个合法的x k>=x都是一个合法的解
因为num1 = num2 => (num1 + num2) % 2 == 0 可以构造一层的满覆盖
所以可以二分x 然后用网络流check

建图：
如果点k为白
建边(s, k, x – v[k])
如果为黑
建边(k, t, x – v[k])
对相邻点u、v (u为白)
建边 (u, v, inf)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define inf (1LL<<50)
#define pa pair<int,int>
#define ll long long 
#define p(x,y) (x-1)*m+y
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll s0,s1;
int c0,c1;
int test,n,m,cnt,S,T;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int a[45][45];
int last[2005],h[2005],q[2005],cur[2005];
bool color[45][45];
struct edge{
    int to,next;ll v;
}e[20005];
void insert(int u,int v,ll w)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
    int head=0,tail=1;
    memset(h,-1,sizeof(h));
    q[0]=S;h[S]=0;
    while(head!=tail)
    {
        int now=q[head];head++;
        for(int i=last[now];i;i=e[i].next)
            if(e[i].v&&h[e[i].to]==-1)
            {
                h[e[i].to]=h[now]+1;
                q[tail++]=e[i].to;
            }
    }
    return h[T]!=-1;
}
ll dfs(int x,ll f)
{
    if(x==T)return f;
    ll w,used=0;
    for(int i=cur[x];i;i=e[i].next)
        if(h[e[i].to]==h[x]+1)
        {
            w=dfs(e[i].to,min(f-used,e[i].v));
            e[i].v-=w;e[i^1].v+=w;
            if(e[i].v)cur[x]=i;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}
ll dinic()
{
    ll tmp=0;
    while(bfs())
    {
        for(int i=S;i<=T;i++)cur[i]=last[i];
        tmp+=dfs(S,inf);
    }
    return tmp;
}
bool check(ll x)
{
    memset(last,0,sizeof(last));
    cnt=1;S=0;T=n*m+1;
    ll tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(color[i][j])
            {
                insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];
                for(int k=0;k<4;k++)
                {
                    int nowx=i+xx[k],nowy=j+yy[k];
                    if(nowx<1||nowy<1||nowx>n||nowy>m)continue;
                    insert(p(i,j),p(nowx,nowy),inf);
                }
            }
            else insert(p(i,j),T,x-a[i][j]);
    if(dinic()==tot)return 1;
    return 0;
}
int main()
{
    test=read();
    while(test--)
    {
        c0=c1=s0=s1=0;
        n=read();m=read();
        int mx=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                a[i][j]=read(),color[i][j]=(i+j)&1;
                mx=max(mx,a[i][j]);
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(color[i][j])s1+=a[i][j],c1++;
                else s0+=a[i][j],c0++;
        if(c0!=c1)
        {
            ll x=(s0-s1)/(c0-c1);
            if(x>=mx)
                if(check(x))
                {
                    printf("%lld\n",x*c1-s1);
                    continue;
                }
            puts("-1");
        }
        else
        {
            if(s0!=s1)
            {
                puts("-1");
                continue;
            }
            ll l=mx,r=inf;
            while(l<=r)
            {
                ll mid=(l+r)>>1;
                if(check(mid))r=mid-1;
                else l=mid+1;
            }
            printf("%lld\n",(ll)l*c1-s1);
        }
    }   
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define inf (1LL<<50)

#define pa pair<int,int>

#define ll long long

#define p(x,y) (x-1)*m+y

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll s0,s1;

int c0,c1;

int test,n,m,cnt,S,T;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

int a[45][45];

int last[2005],h[2005],q[2005],cur[2005];

bool color[45][45];

struct edge{

int to,next;ll v;

}e[20005];

void insert(int u,int v,ll w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

bool bfs()

{

int head=0,tail=1;

memset(h,-1,sizeof(h));

q[0]=S;h[S]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

ll dfs(int x,ll f)

{

if(x==T)return f;

ll w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(f-used,e[i].v));

e[i].v-=w;e[i^1].v+=w;

if(e[i].v)cur[x]=i;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

ll dinic()

{

ll tmp=0;

while(bfs())

{

for(int i=S;i<=T;i++)cur[i]=last[i];

tmp+=dfs(S,inf);

}

return tmp;

}

bool check(ll x)

{

memset(last,0,sizeof(last));

cnt=1;S=0;T=n*m+1;

ll tot=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(color[i][j])

{

insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];

for(int k=0;k<4;k++)

{

int nowx=i+xx[k],nowy=j+yy[k];

if(nowx<1||nowy<1||nowx>n||nowy>m)continue;

insert(p(i,j),p(nowx,nowy),inf);

}

else insert(p(i,j),T,x-a[i][j]);

if(dinic()==tot)return 1;

return 0;

}

int main()

{

test=read();

while(test--)

{

c0=c1=s0=s1=0;

n=read();m=read();

int mx=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

a[i][j]=read(),color[i][j]=(i+j)&1;

mx=max(mx,a[i][j]);

}

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(color[i][j])s1+=a[i][j],c1++;

else s0+=a[i][j],c0++;

if(c0!=c1)

{

ll x=(s0-s1)/(c0-c1);

if(x>=mx)

if(check(x))

{

printf("%lld\n",x*c1-s1);

continue;

}

puts("-1");

}

else

{

if(s0!=s1)

{

puts("-1");

continue;

}

ll l=mx,r=inf;

while(l<=r)

{

ll mid=(l+r)>>1;

if(check(mid))r=mid-1;

else l=mid+1;

}

printf("%lld\n",(ll)l*c1-s1);

}

return 0;

}

« 「POJ1637」Sightseeing tour 「湖北省队互测day6」Asiram »

...

应该还有当 c0=c1,如果s0!=s1,输出－1

hzwer

已改

cgh

黄学长不是return 0 啊是continue吧？

hzwer

QAQ

cgh

这个也是黄学长的号吗、、

伪日常系LordNanoApe

程序有错误，测试数据如下：
1
2 3
0 4 0
3 6 6
正确答案应该是-1

hzwer.com _ Home | http://hzwer.com

「BZOJ2756」[SCOI2012] 奇怪的游戏

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论