感谢@似水流年 的翻译

感谢@FizzyDavid 的提示

题意:

你可以横着刷一串,代价是h;竖着一串代价是v,单独刷一格代价是s

第一眼看起来是什么奇怪的技巧

思考了半天不会...

后来想到网络流,推不出来很抓狂

今天仔细推了一下终于出来了...

最小割即可

S集合:s点源点 所有选的行 没选的列

T集合:t点汇点 所有选的列 没选的行

自然,选某一行的代价是有的, 行-->t 一条有向边代价为h

同理,选某一列的代价是有的, s-->列 一条有向边代价为v

还有,行列都不选,意味着它要单独刷,列-->行 一条有向边代价为c(没选的列-->没选的行要割掉)

这样图就建出来了

之后,求最小割只需要bfs一遍所有从s能到的点都是S集合....

结束....

代码又是250行

#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;
const int maxn=2005;
const int inf=999999999;
struct edge
{
    int y;
    int weight;
    edge * next;
    edge * anti;
};
edge * li[maxn];
edge * new_edge()
{
    static edge a[30005];
    static int top=0;
    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 1;
                que[rail++]=x->y;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t)
{
    int tot=0;
    static int pre[maxn];
    static edge * cur[maxn];
    static edge * path[maxn];
    for (;bfs(s,t);)
    {
        memcpy(cur,li,sizeof(cur));
        int now=s;
        for (;dist[s]!=-1;)
        {
            if (now==t)
            {
                int min_ans=inf;
                int temp;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    min_ans=min(min_ans,path[temp]->weight);
                }
                tot+=min_ans;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    path[temp]->weight-=min_ans;
                    path[temp]->anti->weight+=min_ans;
                }
                now=s;
            }
            edge * x;
            for (x=cur[now];x!=0;x=x->next)
            {
                if ((x->weight!=0)&&(dist[x->y]==dist[now]+1))
                {
                    path[x->y]=x;
                    pre[x->y]=now;
                    cur[now]=x;
                    now=x->y;
                    break;
                }
            }
            if (x==0)
            {
                dist[now]=-1;
                now=pre[now];
            }
        }
    }
    return tot;
}
char a[35][35];
int belong_to[35][35];
int belong_2[35][35];
int n,m;
void find(int x)
{
    int i,j;
    int minx=n,miny=m,maxx=0,maxy=0;
    char y;
    for (i=0;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            if ((belong_to[i][j]==x)||(belong_2[i][j]==x))
            {
                minx=min(minx,i);
                maxx=max(maxx,i);
                miny=min(miny,j);
                maxy=max(maxy,j);
                y=a[i][j];
            }
        }
    }
    printf("%d %d %d %d %c\n",minx+1,miny+1,maxx+1,maxy+1,y);
}
int main()
{
    freopen("painter.in","r",stdin);
    freopen("painter.out","w",stdout);
    scanf("%d%d",&n,&m);
    int h,v,c;
    scanf("%d%d%d",&h,&v,&c);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%s",a[i]);
    }
    int s=0,t=1;
    int sum=2;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            belong_to[i][j]=sum;
            if (a[i][j]!=a[i][j+1])
            {
                insert_edge(sum,t,h);
                sum++;
            }
        }
    }
    int x=sum;
    for (i=0;i<m;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            belong_2[j][i]=sum;
            insert_edge(sum,belong_to[j][i],c);
            if (a[j][i]!=a[j+1][i])
            {
                insert_edge(s,sum,v);
                sum++;
            }
        }
    }
    printf("%d ",max_flow(s,t));
    int tot=0;
    for (i=2;i<x;i++)
    {
        if (dist[i]!=-1)
        {
            tot++;
        }
    }
    for (;i<sum;i++)
    {
        if (dist[i]==-1)
        {
            tot++;
        }
    }
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            if ((dist[belong_to[i][j]]==-1)&&(dist[belong_2[i][j]]!=-1))
            {
                tot++;
            }
        }
    }
    printf("%d\n",tot);
    for (i=2;i<x;i++)
    {
        if (dist[i]!=-1)
        {
            printf("h ");
            find(i);
        }
    }
    for (;i<sum;i++)
    {
        if (dist[i]==-1)
        {
            printf("v ");
            find(i);
        }
    }
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            if ((dist[belong_to[i][j]]==-1)&&(dist[belong_2[i][j]]!=-1))
            {
                printf("s %d %d %c\n",i+1,j+1,a[i][j]);
            }
        }
    }
    return 0;
}