BZOJ1066/SCOI2007/蜥蜴

Posted on By 二价氢

构图……

拆点,每根石柱拆成两个点,一个入一个出,两点间容量为石柱的高度

AC-Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXMAP=25,INF=43456344;//INF still by RANDOM
//--邻接表
struct Edge{int t,v,op,next;}E[MAXMAP*MAXMAP*200];//位置及容量和反向边
int pStart[MAXMAP*MAXMAP*100];//
//--路径
bool vis[MAXMAP*MAXMAP*100];
int pE[MAXMAP*MAXMAP*100],pP[MAXMAP*MAXMAP*100];
//--题干
int R,C,D;
int totE=0;
//--
int S=0,T;
int totT;
inline int GetPN(int x,int y,int l)
{
    return ((x*21+y)*2)+l;
}
void Spfa()
{
    int u;
    memset(vis,0,sizeof(vis));
    memset(pE,-1,sizeof(pE));
    memset(pP,-1,sizeof(pP));
    queue<int>Q;
    Q.push(S);
    vis[S]=true;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();
        for (int up=pStart[u];up;up=E[up].next)
            if (E[up].v>0&&!vis[E[up].t])
            {
                vis[E[up].t]=true;
                pE[E[up].t]=up;
                pP[E[up].t]=u;
                Q.push(E[up].t);
            }
    }
}
int MaxFlow()
{
    int ret=0,tret,u;
    while (1)
    {
        Spfa();
        if (!vis[T])
            break;
        tret=0x3f3f3f3f;
        for (u=T;pP[u]!=-1;u=pP[u])
            tret=min(tret,E[pE[u]].v);
        for (u=T;pP[u]!=-1;u=pP[u])
        {
            E[pE[u]].v-=tret;
            E[E[pE[u]].op].v+=tret;
        }
        ret+=tret;
    }
    return ret;
}
void AddEdge(int u,int v,int c)
{
    int E1=++totE;
    int E2=++totE;
    E[E1].t=v;E[E1].v=c;E[E1].op=E2;E[E1].next=pStart[u];pStart[u]=E1;
    E[E2].t=u;E[E2].v=0;E[E2].op=E1;E[E2].next=pStart[v];pStart[v]=E2;
}
bool Dis(int x1,int y1,int x2,int y2)
{
    return ((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))<=D*D;
}
int main()
{
    char tmp;
    cin>>R>>C>>D;
    for (int i=1;i<=R;i++)
        for (int j=1;j<=C;j++)
            for (int k=1;k<=R;k++)
                for (int l=1;l<=C;l++)
                    if ((i!=k||j!=l)&&Dis(i,j,k,l))
                        AddEdge(GetPN(i,j,1),GetPN(k,l,0),INF);
    for (int i=1;i<=R;i++)
        for (int j=1;j<=C;j++)
        {
            cin>>tmp;
            if (tmp!='0')
                AddEdge(GetPN(i,j,0),GetPN(i,j,1),tmp-'0');
        }
    for (int i=1;i<=R;i++)
        for (int j=1;j<=C;j++)
        {
            cin>>tmp;
            if (tmp=='L')
            {
                totT++;
                AddEdge(S,GetPN(i,j,0),1);
            }
        }
    T=GetPN(R+2,C+2,0);
    for (int i=1;i<=R;i++)
        for (int j=1;j<=C;j++)
            if (Dis(i,j,i,0)||Dis(i,j,0,j)||Dis(i,j,i,C+1)||Dis(i,j,R+1,j))
                AddEdge(GetPN(i,j,1),T,INF);
    cout<<totT-MaxFlow()<<endl;
    return 0;
}