一套题能有两个网络流,醉了...

链接:http://codeforces.com/gym/100729/attachments/download/3754/20112012-northwestern-european-regional-contest-nwerc-2011-en.pdf

题意:

给你一块地

首先:周围一圈必须是草地

其次,每个地方可以把它从水池变为草地(代价为f),草地变成水池(代价为d)

之后水池会被建成游泳池,所以要给草地和水池之间贴瓷砖,代价为b

例如

###

#.#

###

要贴4块瓷砖,在.的四周各贴一块

所以干脆把.变成#可能会更划算

这一题是个网络流-最小割

一套题2个网络流醉了...

还有一题是100728D

S集合:

s点,所有选为#的点

T集合:

t点,所有选为.的点

注意:周围一圈直接变成#,并且统计代价

那么需要加3类边

1,次外围:s-->这个点,代价为z

理由:如果这个点建".",那么要一块额外的瓷砖

2,每个点和周围的点建立一条双向边,代价为z

理由:一个"#"一个"."要一块瓷砖

3,如果某个点是"#",那么向t连一条边代价为d(改为水池)

同理,"."的话,s-->这个点一条边代价为b

===============================

WA了好久

一开始怀疑建图错

后来怀疑网络流错

最后竟然发现是一个小函数错了..

inline int num(int x,int y)
{
    return x*n+y;
}

哦,应该是这样

inline int num(int x,int y)
{
    return x*m+y;
}

恩,总代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    int weight;
    edge * next;
    edge * anti;
};
const int maxn=5005;
const int inf=999999999;
edge * li[maxn];
int top=0;
edge * new_edge()
{
    static edge a[100005];
    return &a[top++];
}
edge * inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int z)
{
    edge * t1=inserts(x,y,z);
    edge * t2=inserts(y,x,0);
    t1->anti=t2;
    t2->anti=t1;
}
int dist[maxn];
bool bfs(int s,int t)
{
    memset(dist,-1,sizeof(dist));
    static int que[maxn];
    int front=0,rail=1;
    que[0]=s;
    dist[s]=0;
    for (;front<rail;front++)
    {
        int now=que[front];
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((x->weight>0)&&(dist[x->y]==-1))
            {
                dist[x->y]=dist[now]+1;
                if (x->y==t) return true;
                que[rail++]=x->y;
            }
        }
    }
    return false;
}
int max_flow(int s,int t)
{
    int tot=0;
    for (;bfs(s,t);)
    {
        static edge * path[maxn];
        static edge * cur[maxn];
        static int pre[maxn];
        memcpy(cur,li,sizeof(cur));
        int now=s;
        for (;dist[s]!=-1;)
        {
            if (now==t)
            {
                int mini=inf;
                int temp;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    mini=min(mini,path[temp]->weight);
                }
                tot+=mini;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    path[temp]->weight-=mini;
                    path[temp]->anti->weight+=mini;
                }
                now=s;
            }
            edge * x;
            for (x=cur[now];x!=0;x=x->next)
            {
                if ((x->weight>0)&&(dist[x->y]==dist[now]+1))
                {
                    pre[x->y]=now;
                    path[x->y]=x;
                    cur[now]=x;
                    now=x->y;
                    break;
                }
            }
            if (x==0)
            {
                dist[now]=-1;
                now=pre[now];
            }
        }
    }
    return tot;
}
char a[55][55];
int n,m;
inline int num(int x,int y)
{
    return x*m+y;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        scanf("%d%d",&m,&n);
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        int i;
        for (i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        memset(li,0,sizeof(li));
        top=0;
        int sum=0;
        for (i=0;i<m;i++)
        {
            if (a[0][i]=='.')
            {
                sum+=y;
                a[0][i]='#';
            }
            if (a[n-1][i]=='.')
            {
                sum+=y;
                a[n-1][i]='#';
            }
        }
        for (i=0;i<n;i++)
        {
            if (a[i][0]=='.')
            {
                sum+=y;
                a[i][0]='#';
            }
            if (a[i][m-1]=='.')
            {
                sum+=y;
                a[i][m-1]='#';
            }
        }
        int s=0,t=1;
        for (i=1;i<n-1;i++)
        {
            int j;
            for (j=1;j<m-1;j++)
            {
                if (i>1)
                {
                    insert_edge(num(i,j),num(i-1,j),z);
                }
                else
                {
                    insert_edge(s,num(i,j),z);
                }
                if (j>1)
                {
                    insert_edge(num(i,j),num(i,j-1),z);
                }
                else
                {
                    insert_edge(s,num(i,j),z);
                }
                if (i<n-2)
                {
                    insert_edge(num(i,j),num(i+1,j),z);
                }
                else
                {
                    insert_edge(s,num(i,j),z);
                }
                if (j<m-2)
                {
                    insert_edge(num(i,j),num(i,j+1),z);
                }
                else
                {
                    insert_edge(s,num(i,j),z);
                }
                if (a[i][j]=='#')
                {
                    insert_edge(s,num(i,j),x);
                }
                else
                {
                    insert_edge(num(i,j),t,y);
                }
            }
        }
        printf("%d\n",sum+max_flow(s,t));
    }
    return 0;
}