bzoj1001: [BeiJing2006]狼抓兔子

/**************************************************************
    Problem: 1001
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:2048 ms
    Memory:149404 kb
****************************************************************/
 
#include<queue>
#include<cstdio>
#include<cstring>
#define mp make_pair
#define pr pair<int,int>
using namespace std;
const int N=1050;
struct pp {int v,nxt,d;} e[N*N*10];
int n,m,head[N*N*2],tot,dis[N*N*2],st,ed;
bool vis[N*N*2];
priority_queue< pr > q;
void add(int u,int v,int d)
{
//  printf("%d->%d : %d\n",u,v,d);
    e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;e[tot].d=d;
    e[++tot].nxt=head[v];head[v]=tot;e[tot].v=u;e[tot].d=d;
}
void dij()
{
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;q.push(mp(0,st));
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u]) continue; vis[u]=1;
        for(int j=head[u];j;j=e[j].nxt)
        {
            int v=e[j].v,d=e[j].d;
            if(dis[v]>dis[u]+d)
            {
                dis[v]=dis[u]+d;
                q.push(mp(-dis[v],v));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);// 3 4
    if(m==1)
    {
        int res=2e9;for(int i=1,x;i<n;i++)
            scanf("%d",&x),res=res>x?x:res;
        printf("%d\n",res);return 0;
    }
    if(n==1)
    {
        int res=2e9;for(int i=1,x;i<m;i++)
            scanf("%d",&x),res=res>x?x:res;
        printf("%d\n",res);return 0;
    }
    st=(n-1)*(m-1)*2+1,ed=st+1;
    for(int i=1;i<=n;i++)
        for(int j=1,x;j<m;j++) 
        {
            scanf("%d",&x);
            if(i==1) add((i-1)*(m-1)*2+j*2,ed,x);
            else if(i==n) add(st,(i-2)*(m-1)*2+(j-1)*2+1,x);
            else add((i-2)*(m-1)*2+(j-1)*2+1,(i-1)*(m-1)*2+j*2,x);
        }
    for(int i=1;i<n;i++)
        for(int j=1,x;j<=m;j++)
        {
            scanf("%d",&x);
            if(j==1) add(st,(i-1)*(m-1)*2+(j-1)*2+1,x);
            else if(j==m) add((i-1)*(m-1)*2+(j-1)*2,ed,x);
            else add((i-1)*(m-1)*2+(j-1)*2,(i-1)*(m-1)*2+(j-1)*2+1,x);
        }
    for(int i=1;i<n;i++)
        for(int j=1,x;j<m;j++) 
        {
            scanf("%d",&x);
            add((i-1)*(m-1)*2+(j-1)*2+1,(i-1)*(m-1)*2+j*2,x);
        }
    dij();printf("%d\n",dis[ed]);
    return 0;
}

/**************************************************************
    Problem: 1001
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:1932 ms
    Memory:117132 kb
****************************************************************/
 
/*
    要拦住所有兔子就要把这个图切断
    就是这个图的最小割  = 最大流 
    注意双向边！ （看成单向结果样例答案只有 11 ） 
*/
#include<cstdio>
#include<queue>
#include<cstring>
#define min(a,b) ((a>b)?(b):(a))
#define inf (0x3fffffff)
using namespace std;
const int N=1e3+50;
struct pp {int v,nxt,c;}e[(N*N)<<3];
int n,m,tot=1,head[N*N],cur[N*N];
int dep[N*N],st,ed;
void add(int u,int v,int c)
{
    e[++tot].nxt=head[u];head[u]=tot;
    e[tot].v=v;e[tot].c=c;
    e[++tot].nxt=head[v];head[v]=tot;
    e[tot].v=u;e[tot].c=c;
}
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
    {
        int c;scanf("%d",&c);add((i-1)*m+j,(i-1)*m+j+1,c);
    }
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++)
    {
        int c;scanf("%d",&c); add((i-1)*m+j,i*m+j,c);
    }
    for(int i=1;i<n;i++)
    for(int j=1;j<m;j++)
    {
        int c;scanf("%d",&c); add((i-1)*m+j,i*m+j+1,c);
    }
    st=n*m+1;ed=st+1;
    add(st,1,inf);add(n*m,ed,inf);
}
bool bfs()
{
    queue<int> q;
    memset(dep,0,sizeof(dep));
    q.push(st); dep[st]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int j=head[u];j;j=e[j].nxt)
        {
            int v=e[j].v;
            if(e[j].c>0&&!dep[v])
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[ed];
}
int dfs(int u,int now)
{
    if(u==ed||now==0) return now;
    int val=0,s;
    for(int&j=cur[u];j;j=e[j].nxt)
    {
        int v=e[j].v;
        if(dep[v]==dep[u]+1&&e[j].c>0)
        {
            val+=(s=dfs(v,min(now-val,e[j].c)));
            e[j].c-=s;e[j^1].c+=s;
            if(val==now) break;
        }
    }
    if(val==0) dep[u]=0;
    return val;
}
int main()
{
    init();  int ans=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(head));
        int res;while(res=dfs(1,inf)) ans+=res;
    }
    printf("%d\n",ans);
    return 0;
}