hlpp.cpp

本人参加ACM竞赛使用的一些算法模板

/*杭州赛区预赛E题的解法
发信站: 逸仙时空 Yat-sen Channel (Tue Oct 11 22:24:15 2005)

这题隐藏了一个网络最小切割的模型(建议看一下lrj书的317页NASA问

题),我自己没想出来，是受了bug和PHOENIX的启发.

来看一下那个函数是怎么与最小割对应的，对每一个点i增加

s->i,c[s][i]=|pi-v0|,i->t,c[i][t]=|pi-v1|,xi=0对应割集中有

s->i(此时最小割集绝不会出现i->t),xi=1对应割集中有i->t(此时不会出现

s->i),对于相邻两点i,j若xi,xj同为0或1,则i->j和j->i一定不在最小

割集中,若xi=0,xj=1,要想构成割集，必须有i->j,若xi=1,xj=0，必须有

j->i

附程序：
*/
#include <iostream>
#include <list>
#define MAX_NODE 405
using namespace std;
typedef int Graph[MAX_NODE][MAX_NODE];
Graph G;
Graph C;                                        //capacity
Graph f;                                        //flow
Graph R;                                        //Residual
int h[MAX_NODE];                        //height
int e[MAX_NODE];                        //excess
int current[MAX_NODE];      //position in the adjacent list of vertices
int deg[MAX_NODE];          //degree
int n;                                          //number of vertices
int s;                                          //source
int t;                                          //sink
int p[MAX_NODE];

void INITIALIZE_PREFLOW()
{
        int u;
        memset(h,0,sizeof(h));
        memset(e,0,sizeof(e));
        memset(f,0,sizeof(f));
        h[s]=n;
        for(u=0;u<n;u++){
                f[s][u]=C[s][u];
                f[u][s]=-C[s][u];
                e[u]=C[s][u];
                e[s]-=C[s][u];
                R[s][u]=C[s][u]-f[s][u];
                R[u][s]=C[u][s]-f[u][s];
        }
}

void PUSH(int u,int v)
{
        int d;
        d=e[u]<R[u][v]?e[u]:R[u][v];
        f[u][v]+=d;
        f[v][u]=-f[u][v];
        R[u][v]=C[u][v]-f[u][v];
        R[v][u]=C[v][u]-f[v][u];
        e[u]-=d;
        e[v]+=d;
}

void RELABEL(int u)
{
        int min_h=INT_MAX,v,i;
        for(i=0;i<deg[u];i++){
                v=G[u][i];
                if (R[u][v]>0&&h[v]<min_h) min_h=h[v];
        }
        h[u]=min_h+1;
}

void DISCHARGE(int u)
{
        int v;
        while(e[u]>0){
                v=G[u][current[u]];
                if (current[u]==deg[u]){
                        RELABEL(u);
                        current[u]=0;
                }
                else if (R[u][v]>0&&h[u]==h[v]+1) PUSH(u,v);
                else current[u]++;
        }
}

int RELABEL_TO_FRONT()
{
        int u,old_height,ret=0;
        list<int> L;
        list<int>::iterator it;
        memset(current,0,sizeof(current));
        INITIALIZE_PREFLOW();
        for(u=0;u<n;u++)if (u!=s&&u!=t) L.push_back(u);
        for(it=L.begin();it!=L.end();it++){
                u=*it;
                old_height=h[u];
                DISCHARGE(u);
                if (h[u]>old_height){
                        L.erase(it);
                        L.push_front(u);
                        it=L.begin();
                }
        }
        for(u=0;u<n;u++) ret+=f[s][u];
        return ret;
}


int main()
{
        int T,Row,Column,v0,v1,i,j,cas=0;
        freopen("input.dat","r",stdin);
        scanf("%d",&T);
        while(T--){
                scanf("%d%d%d%d",&Row,&Column,&v0,&v1);
                s=0;
                t=Row*Column+1;
                n=t+1;
                memset(deg,0,sizeof(deg));
                memset(R,0,sizeof(R));
                memset(C,0,sizeof(C));
                for(i=1;i<=Row*Column;i++) scanf("%d",&p[i]);
                for(i=1;i<=Row*Column;i++){
                        R[s][i]=C[s][i]=abs(p[i]-v0);
                        G[s][deg[s]++]=i;
                        G[i][deg[i]++]=s;
                        R[i][t]=C[i][t]=abs(p[i]-v1);
                        G[i][deg[i]++]=t;
                        G[t][deg[t]++]=i;
                        if (i%Column){
                                j=i+1;
                                R[i][j]=C[i][j]=abs(p[i]-p[j]);
                                R[j][i]=C[j][i]=abs(p[i]-p[j]);
                                G[i][deg[i]++]=j;
                                G[j][deg[j]++]=i;
                        }
                        if (i+Column<=Row*Column){
                                j=i+Column;
                                R[i][j]=C[i][j]=abs(p[i]-p[j]);
                                R[j][i]=C[j][i]=abs(p[i]-p[j]);
                                G[i][deg[i]++]=j;
                                G[j][deg[j]++]=i;
                        }
                }
                printf("Case %d:\n%d\n",++cas,RELABEL_TO_FRONT());
                if (T) printf("\n");
        }
        return 0;
}