题目描述

设有 $N \times N$ 的方格图 $(N \le 9)$ ，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$ 。如下图所示（见样例）:

A

 0  0  0  0  0  0  0  0

 0  0 13  0  0  6  0  0

 0  0  0  0  7  0  0  0

 0  0  0 14  0  0  0  0

 0 21  0  0  0  4  0  0

 0  0 15  0  0  0  0  0

 0 14  0  0  0  0  0  0

 0  0  0  0  0  0  0  0

                         B

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$ ）。
此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和为最大。

输入输出格式

**输入格式：**

输入的第一行为一个整数 $N$ （表示 $N \times N$ 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。

**输出格式：**
只需输出一个整数，表示 $2$ 条路径上取得的最大的和。
输入输出样例
> **输入样例#1：**
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
**输出样例#1：**
67

说明

NOIP 2000 提高组第四题

DP？不存在的

直接拆点建立两条边，值取反，跑最小费用最大流

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define maxn 100010

#define inf 0x3f3f3f3f

using namespace std;

int read()

{

    int x=0,f=1;char s=getchar();

    while('0'>s||s>'9') {if(s=='-') f=-1;s=getchar();}

    while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}

    return x*f;

}

int n,m,S,T;

int ans;

int map[10][10];

int from[maxn],dis[maxn],vis[maxn];

struct edge {

    int u,v,nxt,spend,flow;

}e[maxn];

int head[maxn],tot=1;

void add_edge(int u,int v,int flow,int spend)

{

    e[++tot].u=u;

    e[tot].v=v;

    e[tot].spend=spend;

    e[tot].flow=flow;

    e[tot].nxt=head[u];

    head[u]=tot;

}

void add(int u,int v,int flow,int spend)

{

    add_edge(u,v,flow,spend);

    add_edge(v,u,0,-spend);

}

bool spfa()

{

    memset(dis,inf,sizeof(dis));

    memset(vis,0,sizeof(vis));

    queue<int> q;

    q.push(S);

    dis[S]=0;

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=0;

        for(int i=head[x];i;i=e[i].nxt)

        {

            int v=e[i].v;

            int u=e[i].u;

            int f=e[i].flow;

            int s=e[i].spend;

            if(dis[v]>dis[u]+s&&f)

            {

                dis[v]=dis[u]+s;

                from[v]=i;

                if(!vis[v])

                {

                    q.push(v);

                    vis[v]=1;

                }

            }

        }

    }

    return dis[T]!=inf;

}

int maxflow;

void work()

{

    int mn=inf;

    for(int i=T;i!=S;i=e[from[i]].u)

        mn=min(mn,e[from[i]].flow);

    for(int i=T;i!=S;i=e[from[i]].u)

    {

        e[from[i]].flow-=mn;

        e[from[i]^1].flow+=mn;

        ans+=e[from[i]].spend*mn;

    }

    maxflow+=mn;

}

int calc(int i,int j)

{

    return n*(i-1)+j;

}

int main()

{

    scanf("%d",&n);

    int a,b,c;

    while(233)

    {

        a=read();

        b=read();

        c=read();

        if(!a) break;

        map[a][b]=c;

    }

    S=0;T=200;

    add(S,1,2,0);

    add(n*n+100,T,inf,0);

    for(int i=1;i<=n;++i)

    {

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

        {

            int newx=i+1;

            int newy=j+1;

            if(newx>=1&&newx<=n)

            {

                add(calc(i,j)+100,calc(newx,j),inf,0);

                //printf("a[%d][%d]->a[%d][%d] ",i,j,newx,j);

            }

            if(newy>=1&&newy<=n)

            {

                add(calc(i,j)+100,calc(i,newy),inf,0);

                //printf("a[%d][%d]->a[%d][%d]",i,j,i,newy);

            }

        }

    }

    for(int i=1;i<=n;++i)

    {

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

        {

            add(calc(i,j),calc(i,j)+100,1,-map[i][j]);

            add(calc(i,j),calc(i,j)+100,1,0);

        }

    }

    while(spfa()) work();

    printf("%d",-ans);

    return 0;

}