begin.BZOJ 1383: 三取方格数

题目大意:给你一个矩阵，每个格子有一个值，现在你要从左上角走到右下角(走3次），使得经过路径的权值和最大。

　　　　每个格子的值只能取一次，取完后变为0，输出走完三次后最大的权值和。

题目思路:费用流做法，对于每个格子拆点，因为权值只有第一次能取，所以将每个格子拆为两条边，一条边容量为1，费用为格子的权值，另一条边容量2，费用0。

　　　相邻格子间连边，容量3，费用0。再建立源点S 与左上角第一个格子连边容量3，费用0。汇点 T 与右下角最后一个格子连边，容量3，费用0。跑费用流累加费用即可。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include<functional>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 100005

#define maxn 10005

typedef pair<int,int> PII;

typedef long long LL;

int n,m,ans,S,T,cost;

char pic[][];

int num[][];

int vis[maxn],pre[maxn],d[maxn];

struct Node{

    int to,next,f,c;

    Node(){}

    Node(int a,int b,int _c,int d):to(a),next(b),f(_c),c(d){}

}node[N];int head[maxn],hcnt;

queue<int>q;

inline void add(int x,int y,int f,int c){

    node[hcnt]=Node(y,head[x],f,c);head[x]=hcnt++;

    node[hcnt]=Node(x,head[y],,-c);head[y]=hcnt++;

}

void init(){

    mst(head,-);hcnt=;

    S=;T=n*n*+;

    add(S,,,);add(num[n][n]+n*n,T,,);

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

        if(i+<=n)add(num[i][j]+n*n,num[i+][j],,);

        if(j+<=n)add(num[i][j]+n*n,num[i][j+],,);

        add(num[i][j],num[i][j]+n*n,,);

        add(num[i][j],num[i][j]+n*n,,pic[i][j]-'');

    }

}

int spfa(){

    pre[S]=pre[T]=-;

    mst(vis,);mst(d,-);d[S]=;

    q.push(S);

    while(!q.empty()){

        int x=q.front();q.pop();

        vis[x]=;

        for(int i=head[x];~i;i=node[i].next){

            int e=node[i].to;

            if(node[i].f&&d[e]<d[x]+node[i].c){

                pre[e]=i^;

                d[e]=d[x]+node[i].c;

                if(!vis[e]){

                    q.push(e);

                    vis[e]=;

                }

            }

        }

    }

    return pre[T]!=-;

}

void mcmf(){

    init();

    while(spfa()){

        int fl=inf;

        for(int i=pre[T];~i;i=pre[node[i].to])

            fl=min(fl,node[i^].f);

        for(int i=pre[T];~i;i=pre[node[i].to]){

            node[i].f+=fl;node[i^].f-=fl;

        }

        cost+=d[T];

    }

    printf("%d\n",cost);

}

int main() {

    int i,j,group,x,y,Case=;

    scanf("%d",&n);

    for(i=;i<=n;++i){

        scanf("%s",pic[i]+);

        for(j=;j<=n;++j)

            num[i][j]=++Case;

    }

    mcmf();

    return ;

}

巴特西

begin.BZOJ 1383: 三取方格数

最新文章

热门文章