SCU3033 Destroying a Painting（最小费用最大流）

题目大概说有一个有n*m个格子的画板，画板上每个格子都有颜色，现在要把所有格子的颜色改成红、绿或者蓝，改变的代价是二者RGB值的曼哈顿距离，还要求红绿蓝格子个数的最大值和最小值要尽可能接近，问最少的代价是多少。

红绿蓝三色的个数是可以直接确定的，分别考虑几个情况就OK了，然后就是根据红绿蓝的个数构图跑最小费用最大流。。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 using namespace std;
  6 #define INF (1<<30)
  7 #define MAXN 444
  8 #define MAXM 444*888
  9 struct Edge{
 10     int u,v,cap,cost,next;
 11 }edge[MAXM];
 12 int head[MAXN];
 13 int NV,NE,vs,vt;
 14 
 15 void addEdge(int u,int v,int cap,int cost){
 16     edge[NE].u=u; edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;
 17     edge[NE].next=head[u]; head[u]=NE++;
 18     edge[NE].u=v; edge[NE].v=u; edge[NE].cap=0; edge[NE].cost=-cost;
 19     edge[NE].next=head[v]; head[v]=NE++;
 20 }
 21 bool vis[MAXN];
 22 int d[MAXN],pre[MAXN];
 23 bool SPFA(){
 24     for(int i=0;i<NV;++i){
 25         vis[i]=0;
 26         d[i]=INF;
 27     }
 28     vis[vs]=1;
 29     d[vs]=0;
 30     queue<int> que;
 31     que.push(vs);
 32     while(!que.empty()){
 33         int u=que.front(); que.pop();
 34         for(int i=head[u]; i!=-1; i=edge[i].next){
 35             int v=edge[i].v;
 36             if(edge[i].cap && d[v]>d[u]+edge[i].cost){
 37                 d[v]=d[u]+edge[i].cost;
 38                 pre[v]=i;
 39                 if(!vis[v]){
 40                     vis[v]=1;
 41                     que.push(v);
 42                 }
 43             }
 44         }
 45         vis[u]=0;
 46     }
 47     return d[vt]!=INF;
 48 }
 49 int MCMF(){
 50     int res=0;
 51     while(SPFA()){
 52         int flow=INF,cost=0;
 53         for(int u=vt; u!=vs; u=edge[pre[u]].u){
 54             flow=min(flow,edge[pre[u]].cap);
 55         }
 56         for(int u=vt; u!=vs; u=edge[pre[u]].u){
 57             edge[pre[u]].cap-=flow;
 58             edge[pre[u]^1].cap+=flow;
 59             cost+=flow*edge[pre[u]].cost;
 60         }
 61         res+=cost;
 62     }
 63     return res;
 64 }
 65 
 66 inline void in(int &ret){
 67     char c; ret=0;
 68     while(c=getchar(),c<'0'||c>'9');
 69     while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
 70 }
 71 int n,m,R[22][22],G[22][22],B[22][22];
 72 int get(int r,int g,int b){
 73     vs=n*m+3; vt=vs+1; NV=vt+1; NE=0;
 74     memset(head,-1,sizeof(head));
 75     addEdge(n*m,vt,r,0);
 76     addEdge(n*m+1,vt,g,0);
 77     addEdge(n*m+2,vt,b,0);
 78     for(int i=0; i<n; ++i){
 79         for(int j=0; j<m; ++j){
 80             addEdge(vs,i*m+j,1,0);
 81             addEdge(i*m+j,n*m,1,abs(255-R[i][j])+G[i][j]+B[i][j]);
 82             addEdge(i*m+j,n*m+1,1,R[i][j]+abs(255-G[i][j])+B[i][j]);
 83             addEdge(i*m+j,n*m+2,1,R[i][j]+G[i][j]+abs(255-B[i][j]));
 84         }
 85     }
 86     return MCMF();
 87 }
 88 int main(){
 89     int t;
 90     in(t);
 91     for(int cse=1; cse<=t; ++cse){
 92         in(n); in(m);
 93         for(int i=0; i<n; ++i){
 94             for(int j=0; j<m; ++j){
 95                 in(R[i][j]); in(G[i][j]); in(B[i][j]);
 96             }
 97         }
 98         int ans=INF;
 99         if(n*m%3==0){
100             ans=min(ans,get(n*m/3,n*m/3,n*m/3));
101         }else if(n*m%3==1){
102             ans=min(ans,get(n*m/3+1,n*m/3,n*m/3));
103             ans=min(ans,get(n*m/3,n*m/3+1,n*m/3));
104             ans=min(ans,get(n*m/3,n*m/3,n*m/3+1));
105         }else{
106             ans=min(ans,get(n*m/3+1,n*m/3+1,n*m/3));
107             ans=min(ans,get(n*m/3+1,n*m/3,n*m/3+1));
108             ans=min(ans,get(n*m/3,n*m/3+1,n*m/3+1));
109         }
110         printf("Case %d: %d
",cse,ans);
111     }
112     return 0;
113 }