about 4 years ago

theory:
1、可以把黑白棋子图转化为将黑子移动至目标位置
2、需要移动的黑子是起始位置,而目标为黑子初始为白子的格子是目标位置
注意只有这两个点的容量限制中奇数有意义,其他点必定容量限制偶数才有意义
所以建图时只有从出发黑子的边 以及 进入目标白字的边 容量为(cap+1)/2【不要弄混!!】
3、因为每个点流进流出的容量限制可能不一样,所以将每个点一分为三,用三点之间连着的两条边限制。
网络流神建图!!!

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#define maxn 1250
#define maxm 10001
#define inf 1000000000
using namespace std;
int next[maxm],point[maxn],u[maxm],v[maxm],w[maxm],cap[maxm],flow[maxm];
bool can[maxn];
queue<int>q;
int d[maxn],road[maxn];
int n,m,start,til,widen=-1,into=0,outo=0;
char map[21][21]={0};
const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
void addedge(int x,int y,int flowing,int value)
{
    widen++;
    next[widen]=point[x];point[x]=widen;u[widen]=x;v[widen]=y;cap[widen]=flowing;w[widen]=value;
    widen++;
    next[widen]=point[y];point[y]=widen;u[widen]=y;v[widen]=x;cap[widen]=0;w[widen]=-value;
}
int change(int x,int y) {return (x*m+y);}
inline bool init()
{
    int i,j,k,x,y;char c;
    scanf("%d%d",&n,&m);
    start=n*m*3+1,til=n*m*3+2;
    for (i=0;i<n;i++)  scanf("%s",map[i]);
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    {
        c=getchar();
        while (c!='0'&&c!='1')c=getchar();
        if (c==map[i][j]) map[i][j]=0;
        else
        {
            k=change(i,j);
            if (map[i][j]=='1') into++,map[i][j]=1,addedge(start,k+n*m,1,0);
            if(c=='1') outo++,map[i][j]=2,addedge(k+n*m,til,1,0);
        }
    }
    if (into!=outo) return false;
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    {
        c=getchar();k=change(i,j);
        while (!(c<='9'&&c>='0'))c=getchar();
        if (map[i][j]==1)addedge(k+n*m,k+n*m*2,(c-'0'+1)/2,0);
          else addedge(k+n*m,k+n*m*2,(c-'0')/2,0);
        if (map[i][j]==2) addedge(k,k+n*m,(c-'0'+1)/2,0);
          else addedge(k,k+n*m,(c-'0')/2,0);
    }
    for (i=0;i<n;i++)
      for (j=0;j<m;j++)
         for (k=0;k<8;k++)
         {
            x=i+dx[k];y=j+dy[k];
            if (x>=0&&x<n&&y>=0&&y<m)
                addedge(change(i,j)+n*m*2,change(x,y),inf,1);
         }
    return true;
}
bool spfa()
{   int a,k;
    memset(d,0x7f,sizeof(d));
    d[start]=0;can[start]=true;q.push(start);
    while (!q.empty())
    {
        a=q.front();q.pop();
        for (k=point[a];k!=-1;k=next[k])
        {
            if (cap[k]-flow[k]>0&&d[v[k]]>d[a]+w[k])
            {
                d[v[k]]=d[a]+w[k];
                road[v[k]]=k;
                if (!can[v[k]])
                {
                    can[v[k]]=true;
                    q.push(v[k]);
                }
            }
        }
        can[a]=false;
    }
    if (d[til]>inf) return false;
    return true;
}
void mcmf()
{
    int now,cost=0,flowing=0;
    while(true)
    {
        if (!spfa()) break;
        now=til;cost+=d[til];flowing+=1;
        while (now!=start)
        {
            flow[road[now]]++;
            flow[road[now]^1]--;
            now=u[road[now]];
        }
    }
    if (flowing==into) printf("%d\n",cost);
    else printf("-1\n");
}
int main()
{
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    if (init()) mcmf();
      else printf("-1\n");
}
← 【bzoj3578】【thinking】【set】GTY的人类基因组计划2 【bzoj1492】【cdq分治】【整体二分】【动态凸包】货币兑换 →
 
comments powered by Disqus