题目描述
设有 $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;
}