【bzoj1311】最优压缩

2015.06.18 18:14 Thu | 26次阅读 | 旧日oi | 固定链接 | 源码

自己看题吧……
题也很简单,和文理分科基本一样……看代码就懂了

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define M 1000005
#define N 2005
#define inf 0x3f3f3f3f3f3f3f3fll
#define pos(x,y) ((x-1)*m+y)
struct edge
{
    int to,next;
    ll flow;
}e[M];
int h[N],tp;
void ae(int u,int v,ll w)
{
    e[tp].to=v;e[tp].next=h[u];
    e[tp].flow=w;h[u]=tp++;
}
void add(int u,int v,ll w)
{
    ae(u,v,w);ae(v,u,0);
}
int n,m,v0,v1,S,T;
queue<int> q;
ll dis[N];
ll a[N][N];
bool bfs()
{
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty()) q.pop();q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
ll dfs(int u,ll limit)
{
    if(u==T) return limit;
    ll cost=0,tmp;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(limit==cost) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
ll dinic()
{
    ll ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
int main()
{
    cin>>n>>m>>v0>>v1;
    S=0;T=n*m+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%lld",&a[i][j]);
        add(S,pos(i,j),abs(a[i][j]-v0));
        add(pos(i,j),T,abs(a[i][j]-v1));
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
        add(pos(i,j),pos(i,j+1),abs(a[i][j]-a[i][j+1]));
    for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)
        add(pos(i,j),pos(i,j-1),abs(a[i][j]-a[i][j-1]));
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++)
        add(pos(i,j),pos(i+1,j),abs(a[i][j]-a[i+1][j]));
    for(int i=2;i<=n;i++)
    for(int j=1;j<=m;j++)
        add(pos(i,j),pos(i-1,j),abs(a[i][j]-a[i-1][j]));
    printf("%lld\n",dinic());
}```