题目大意：
题目链接：https://jzoj.net/senior/#main/show/4802
这一天,Hnsdfz信息组的众人决定上岳麓山玩.岳麓山上的可以探险的地方非常多,而信息组的Oier们給每一个地方都设定了一个危险值,代表探险这个景点需要承担的危险,而整个岳麓山可以抽象为由n行数字组成的数字梯形.而梯形顶端有m个数字,在每个数字处可以往左上或右上移动 ( (i,j) 可以到 (i-1,j) 或 (i-1,j-1), (i,j)表示输入文件中数字梯形的第i行第j列 ),形成一条从梯形底至顶的路径.
而一开始,每个人都觉得如果走过别人走过的地方就太没个性了.于是有
任务一: 找出m条完全不相交的至底至顶的路径. (不可以重复经过点, 也不可以重复经过边)
但略一思考,又都觉得如果限定这么死,那就太无趣了,于是有:
任务二: 找出m条仅在数字处相交的路径. (可以重复经过点, 但不可以重复经过边. 在山顶相遇也是允许的)
现在,做为整个浏览计划的发起者,你要计算出对于任务一与任务二,每个人观赏线路所能经受的最小危险. (所有人在所有地方获得的危险值总和 最小)
思路：
一看这道题就想起了「网络流24题-数字梯形问题」。虽然之前没有做过
这两道题基本就是重题吧。除了这道题只有两问，数据大了一些，而且求的是最小值。
所以思路就看这里吧
代码：
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rr register
using namespace std;
const int N=20010,Inf=1e9;
int n,m,S,T,T_,cost,maxn,tot,head[N],dis[N],map[210][210],pre[N];
bool vis[N];
struct edge
{
int next,to,from,flow,cost;
}e[N*4];
int C(int x,int y)
{
return (m+m+x-2)*(x-1)/2+y;
}
void add(int from,int to,int flow,int cost)
{
e[++tot].to=to;
e[tot].from=from;
e[tot].flow=flow;
e[tot].cost=cost;
e[tot].next=head[from];
head[from]=tot;
}
bool spfa()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(S);
dis[S]=0; vis[S]=1;
while (q.size())
{
int u=q.front(),v;
q.pop();
vis[u]=0;
for (rr int i=head[u];~i;i=e[i].next)
{
v=e[i].to;
if (e[i].flow&&dis[v]>dis[u]+e[i].cost)
{
dis[v]=dis[u]+e[i].cost;
pre[v]=i;
if (!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
return dis[T]<Inf;
}
void addflow()
{
int minflow=Inf;
for (rr int x=T;x!=S;x=e[pre[x]].from)
minflow=min(minflow,e[pre[x]].flow);
for (rr int x=T;x!=S;x=e[pre[x]].from)
{
e[pre[x]].flow-=minflow;
e[pre[x]^1].flow+=minflow;
}
cost+=dis[T]*minflow;
}
int MCMF()
{
while (spfa())
addflow();
return cost;
}
void make(int val)
{
tot=1;
memset(head,-1,sizeof(head));
for (rr int i=1;i<=n;i++)
for (rr int j=1;j<=m+i-1;j++)
{
add(C(i,j),C(i,j)+maxn,val,map[i][j]);
add(C(i,j)+maxn,C(i,j),0,-map[i][j]);
if (i<n)
{
add(C(i,j)+maxn,C(i+1,j),1,0);
add(C(i+1,j),C(i,j)+maxn,0,0);
add(C(i,j)+maxn,C(i+1,j+1),1,0);
add(C(i+1,j+1),C(i,j)+maxn,0,0);
}
}
for (rr int i=1;i<=m;i++)
{
add(S,C(1,i),val,0);
add(C(1,i),S,0,0);
}
for (rr int i=1;i<=m+n-1;i++)
{
add(C(n,i)+maxn,T_,val,0);
add(T_,C(n,i)+maxn,0,0);
}
add(T_,T,m,0);
add(T,T_,0,0);
cost=0;
}
int main()
{
scanf("%d%d",&n,&m);
for (rr int i=1;i<=n;i++)
for (rr int j=1;j<=m+i-1;j++)
scanf("%d",&map[i][j]);
S=20009; T_=20008; T=20007;
maxn=C(n,n+m-1);
make(1); printf("%d
",MCMF());
make(m); printf("%d
",MCMF());
return 0;
}