bzoj1311: 最优压缩

Description

其中: Auv是与Aij相邻的像素(为了简化,认为(i-1,j),(i+1,j,(i,j-1),(i,j+1)为相邻元素); Wij取值0或者1,表示Aij修改后取V0或者V1. E的定义直观上的理解是,当修改了A之后,各像素上的值与原来的值相差了多少,以及相邻的像素对比程度的变化.为了图像的保真度,我们希望E的值越小越好.

Input

第一行二个整数N,M(1<=N,M<=35) 第二行二个整数V0,V1 接下来N行M列,对应矩阵元素Aij

Output

一个数E,表示最小可能的估价值

Sample Input

1 2
0 255
10 20

Sample Output

题解：

二元组建图：http://www.cnblogs.com/chenyushuo/p/5146626.html

直接二元组建图即可，没有坑。。。。。

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 1600

 #define maxm 20000

 #define inf 1061109567

 using namespace std;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 int n,m,v0,v1,a[][],idx,pos[][];

 struct flow{

     int s,t,tot,now[maxn],son[maxm],pre[maxm],val[maxm];

     int dis[maxn],head,tail,list[maxn];

     bool bo[maxn];

     void init(){s=,t=n*m+,tot=,memset(now,,sizeof(now));}

     void put(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}

     void add(int a,int b,int c){put(a,b,c),put(b,a,);}

     bool bfs(){

         memset(bo,,sizeof(bo));

         head=,tail=,list[]=s,dis[s]=,bo[s]=;

         while (head<tail){

             int u=list[++head];

             for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])

                 if (val[p]&&!bo[v]) bo[v]=,dis[v]=dis[u]+,list[++tail]=v;

         }

         return bo[t];

     }

     int dfs(int u,int rest){

         if (u==t) return rest;

         int ans=;

         for (int p=now[u],v=son[p];p&&rest;p=pre[p],v=son[p])

             if (val[p]&&dis[v]==dis[u]+){

                 int d=dfs(v,min(rest,val[p]));

                 val[p]-=d,val[p^]+=d,ans+=d,rest-=d;

             }

         if (!ans) dis[u]=-;

         return ans;

     }

     int dinic(){

         int ans=;

         while (bfs()) ans+=dfs(s,inf);

         return ans;

     }

 }f;

 const int dx[]={,};

 const int dy[]={,};

 int main(){

     read(n),read(m),read(v0),read(v1),f.init();

     for (int i=;i<=n;i++) for (int j=;j<=m;j++) read(a[i][j]),pos[i][j]=++idx;

     for (int i=;i<=n;i++) for (int j=;j<=m;j++){

         f.add(f.s,pos[i][j],abs(a[i][j]-v0)),f.add(pos[i][j],f.t,abs(a[i][j]-v1));

         for (int k=;k<;k++){

             int x=i+dx[k],y=j+dy[k];

             if (x<=||x>n||y<=||y>m) continue;

             f.add(pos[i][j],pos[x][y],abs(a[i][j]-a[x][y])),f.add(pos[x][y],pos[i][j],abs(a[i][j]-a[x][y]));

         }

     }

     printf("%d\n",f.dinic());

     return ;

 }

秒客网