[CQOI2012]交换棋子

序:

  • 最近复习网络流,就多写几个题玩…

题面:

  • 有一个n行m列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与m_{ij}次交换。

分析:

  • 题目要求每一个位置只能经历m_{ij}次交换,我们先思考,假设没有这个条件我们该怎么写…
  • 首先我们把所有白点忽略,因为只要黑点满足了,剩下的白点也满足了..
  • 我们从源点向所有初始有黑点的方格里连一条流量是1,费用是0的边,然后我们再从终止状态里那些有黑点的位置连一条流量是1费用是0的边到汇点…
  • 然后我们对于一个位置向其四周的点连流量是INF费用是1的边,跑一边最小费用最大流就好了…
  • 然后我们考虑加上限制,我们发现对于一个位置,我们只有进入出去两种选项,那么我们可以把每一个位置分成三个点一个进一个出一个过渡…进点到过渡点和过渡点按到出点的流量上限应该相同,但是如果这个点分配的次数多了该给谁呢?
  • 我们考虑以下三种情况:
  1. 该点初始是白点,终止是黑点,那么进要比出多一次所以分给进
  2. 该点初始是黑点,终止是白点,那么出要比进多一次所以分给出
  3. 该点初始,终止颜色相同,那么分给谁都没事..

– 这些边费用都是0…
– 最后我们给相邻的方块出 进连线就好了,方法和之前的一样…
– 最后跑一次最小费用最大流就OK了…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());   
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int mv[]={-1,0,1};
int n,m,s,t,sum,ans;
int GS[25][25],GT[25][25],times[25][25];
struct Edge{int next,to,flow,cost;}edge[N];
int head[N],cnt=1,cur[N];
void add(int from,int to,int flow,int cost){edge[++cnt]={head[from],to,flow,cost};head[from]=cnt;}
void insert(int from,int to,int flow,int cost){add(from,to,flow,cost);add(to,from,0,-cost);}
int vis[2000],val[2000];
P last[2000];
int SPFA()
{
    deque<int> de;
    memset(vis,0,sizeof(vis));
    memset(val,inf,sizeof(val));
    de.push_back(s);val[s]=0;vis[s]=1;
    while(!de.empty())
    {
        int now=de.front();de.pop_front();vis[now]=0;
        for(int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(!edge[i].flow) continue;
            if(val[to]>val[now]+edge[i].cost) 
            {
                val[to]=val[now]+edge[i].cost;
                last[to]=P(now,i);
                if(!vis[to])
                    de.push_back(to),vis[to]=1;
            }
        }
    }
    if(val[t]!=inf) return val[t];
    return -1;
}
signed main()
{
    read(n),read(m);
    s=n*m*3+1,t=s+1;
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        for(int j=1;j<=m;j++)
            GS[i][j]=s[j-1]-'0';
    }
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        for(int j=1;j<=m;j++)
            GT[i][j]=s[j-1]-'0';
    }
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        for(int j=1;j<=m;j++)
            times[i][j]=s[j-1]-'0';
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int sit=(i-1)*m+j-1;sit*=3;
            if(GS[i][j]) insert(s,sit+2,1,0),sum++; 
            if(GT[i][j]) insert(sit+2,t,1,0);
            insert(sit+1,sit+2,times[i][j]/2,0);
            insert(sit+2,sit+3,times[i][j]/2,0);
            if(times[i][j]%2)
            {
                if(!GS[i][j]&&GT[i][j]) insert(sit+1,sit+2,1,0);
                if(GS[i][j]&&!GT[i][j]) insert(sit+2,sit+3,1,0);
            }
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int sit=(i-1)*m+j-1;sit*=3;
            for(int k=0;k<=2;k++)
                for(int l=0;l<=2;l++)
                    if(i+mv[k]>=1&&i+mv[k]<=n&&j+mv[l]>=1&&j+mv[l]<=m)
                    {
                        int sit2=(i+mv[k]-1)*m+j+mv[l]-1;sit2*=3;
                        insert(sit2+3,sit+1,inf,1);
                        insert(sit+3,sit2+1,inf,1);
                    }
        }
    while(true)
    {
        int flag=SPFA(),now=t;
        if(flag==-1) break;
        while(now!=s)
        {
            edge[last[now].second].flow-=1;
            edge[last[now].second^1].flow+=1;
            now=last[now].first;
        }
        ans+=flag;sum--;
    }
    if(sum) puts("-1");
    else printf("%d\n",ans);
    return 0;
}   

关于“[CQOI2012]交换棋子”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注