时间限制：5秒 内存限制：64M
【问题描述】
由于控制程序出错，动物园的笼子无缘无故被打开，所有动物展开了一次大逃亡。整个城市是一个网络，另外每个单位方格都有一条从左上到右下的对角线，其中动物园在左上角，动物们的目的地在右下角。所有道路（即网格的边和对角线）都是双向的。
每条道路上都有一个正整数权值，代表拦截着条边所需要的工作人员数，如图所示。你的任务是排尽量少的工作人员，使动物无法从动物园走到目的地（动物只能经过没有被拦截的边）。
【输入格式】
输入仅一组数据。第一行为两个整数n和m(3<=n,m<=1000)，即网格的行数和列数。以下n行每行m-1个整数，即拦截每条横边所需人数。以下n-1行每行有m个整数，即拦截每条竖边所需人数。以下n-1行每行m-1个整数，表示拦截每条对角边所需人数。上述边的排列顺序为从上到下从左到右。所有权值均不超过10^6的正整数。输入结束标志为n=m=0。输入文件大小约16MB。
【输出格式】
输出需要派遣工作人员总数。
【输入样例】
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
0 0
【输出样例】
Minimum=14
【数据范围】
3<=n,m<=1000，所有权值均为不超过10^6的正整数。
【来源】
大白书341页，uva1376
BZOJ1001
这道题不看数据范围是道水题，看了就是神题了。
我们很容易想到最小割，然后下意识的用网络流求最大流，但稳稳的超时，一百万个点的最大流肯定超时。但我们并想不到任何优化的方法，网络流直接做根本过不了。
接下来就是神奇的定理和推论了，神犇的解答方案
我们按招这种方法建图，把每一个三角形看成一个点，每个边看成连接相临的2个三角形，边界的上右连接s，左下连接t，然后直接跑dij或者spfa就好。
代码如下：
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000005;
const ll inf=20000000000005ll;
struct edge
{
int u,v,next;
ll f,c;
}e[maxn*10];
int f[maxn],s,t,cur[maxn],d[maxn],cnt=-1,q[maxn*10],n,m;
void add(int u,int v,ll F){
e[++cnt]=(edge){u,v,f[u],F,0};f[u]=cnt;
e[++cnt]=(edge){v,u,f[v],0,0};f[v]=cnt;
}
bool bfs(){
int frond=0,root=0;
memset(d,0,sizeof(d));
q[root++]=s;
d[s]=1;
while(root!=frond)
{
int i=q[frond++];
for(int k=f[i];k!=-1;k=e[k].next)
{
int j=e[k].v;
if(d[j]||e[k].f==e[k].c) continue;
d[j]=d[i]+1;
q[root++]=j;
}
}
return d[t];
}
ll dfs(int i,ll a){
if(i==t||a==0) return a;
ll F,flow=0;
for(int &k=cur[i];k!=-1;k=e[k].next)
{
int j=e[k].v;
if(d[j]==d[i]+1&&(F=dfs(j,min(a,(ll)e[k].f-e[k].c))))
{
a-=F;
flow+=F;
e[k].c+=F;
e[k^1].c-=F;
if(!a) break;
}
}
return flow;
}
ll dinic(){
ll flow=0;
while(bfs())
{
memcpy(cur,f,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
int K(int i,int j){
return (i-1)*m+j;
}
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch<='9'&&ch>='0')
{
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
s=1,t=n*m;
for(int i=s;i<=t;i++) f[i]=-1;
int x,y,w;
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
{
x=read();
add(K(i,j),K(i,j+1),x);
add(K(i,j+1),K(i,j),x);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
{
x=read();
add(K(i,j),K(i+1,j),x);
add(K(i+1,j),K(i,j),x);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
{
x=read();
add(K(i,j),K(i+1,j+1),x);
add(K(i+1,j+1),K(i,j),x);
}
printf("Minimum=");
cout<<dinic();
return 0;
}