BZOJ1001-[BeiJing2006]狼抓兔子(对偶图)

题目链接:BZOJ1001-BeiJing2006狼抓兔子

题意:

给一个网格图,求其最小割。

题解:

A)把平面图转化为对偶图进行最短路求解。注意每个点的序号QAQ。

B)直接裸网络流。

参考代码:

A)对偶图最短路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf= 0x7FFFFFFF;
const int MAXN=3e6+9;
const int MAXM=4e6+9;
int n,m;
struct Edge
{
    int v,w,nxt;
} edge[MAXM*2];
int fir[MAXN],cnt=0;
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node
{
    int u;
    int d;
    node(int u,int d):u(u),d(d) {}
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
bool used[MAXN];
int dis[MAXN];
void dijkstra(int st)
{
    priority_queue<node> que;
    while(!que.empty())
        que.pop();
    for(int i=0;i<=(n-1)*(m-1)*2+1;i++)
        dis[i]=inf;
    dis[st]=0;
    que.push(node(st,dis[st]));
    memset(used,0,sizeof(used));
    while(!que.empty())
    {
        int u=que.top().u;
        que.pop();
        if(used[u])
            continue;
        used[u]=1;
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(used[v])
                continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                que.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    memset(fir,-1,sizeof(fir));
    scanf("%d%d",&n,&m);
    if(n==1||m==1)
    {
        int ans=inf;
        for(int i=1;i<max(n,m);i++)
        {
            int w;
            scanf("%d",&w);
            ans=min(ans,w);
        }
        printf("%d\n",ans);
        return 0;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<m; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(i==1)
            {
                u=0;
                v=j*2;
            }
            else    if(i==n)
            {
                u=((i-2)*(m-1)+j)*2-1;
                v=(n-1)*(m-1)*2+1;
            }
            else
            {
                u=((i-2)*(m-1)+j)*2-1;
                v=((i-1)*(m-1)+j)*2;
            }
            addedge(u,v,w);
            addedge(v,u,w);
        }
    for(int i=1; i<n; i++)
        for(int j=1; j<=m; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(j==1)
            {
                u=((i-1)*(m-1)+j)*2-1;
                v=(n-1)*(m-1)*2+1;
            }
            else    if(j==m)
            {
                u=0;
                v=((i-1)*(m-1)+j-1)*2;
            }
            else
            {
                u=((i-1)*(m-1)+j-1)*2;
                v=((i-1)*(m-1)+j-1)*2+1;
            }
            addedge(u,v,w);
            addedge(v,u,w);
        }
    for(int i=1; i<n; i++)
        for(int j=1; j<m; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            u=((i-1)*(m-1)+j)*2-1;
            v=((i-1)*(m-1)+j)*2;
            addedge(u,v,w);
            addedge(v,u,w);
        }
    dijkstra(0);
    printf( "%d\n",dis[(n-1)*(m-1)*2+1] );
    return 0;
}

B)dinic最大流

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
    int v,w,nxt;
}edge[6000000];
int n,m,cnt,st,ed;
int fir[1001*1001],depth[1001*1001],cur[1001*1001];
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
int dfs(int u,int flow)
{
    if(u==ed)
        return flow;
    for(int& i=cur[u]; i!=-1; i=edge[i].nxt)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(depth[v]==depth[u]+1&&w!=0)
        {
            int di=dfs(v,min(flow,w));
            if(di>0)
            {
                edge[i].w-=di;
                edge[i^1].w+=di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs()
{
    queue<int> q;
    while(!q.empty())
        q.pop();
    memset(depth,0,sizeof(depth));
    depth[st]=1;
    q.push(st);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(depth[v]==0&&w>0)
            {
                depth[v]=depth[u]+1;
                q.push(v);
            }
        }
    }
    if(depth[ed]>0)
        return 1;
    else
        return 0;
}
int dinic()
{
    int tot=0;
    while(bfs())
    {
        for(int i=1; i<=n*m; i++)
            cur[i]=fir[i];
        //memset(cur,0,sizeof(cur));
        while(int temp=dfs(st,inf))
            tot+=temp;
    }
    return tot;
}
int main()
{
    scanf("%d%d",&n,&m);
    cnt=0;
    memset(fir,-1,sizeof(fir));
    for(int i=1;    i<=n;   i++)
    {
        for(int j=1;    j<=m-1; j++)
        {
            int w;
            scanf("%d",&w);
            addedge((i-1)*m+j,(i-1)*m+j+1,w);
            addedge((i-1)*m+j+1,(i-1)*m+j,w);
        }
    }
    for(int i=1;    i<=n-1; i++)
    {
        for(int j=1;    j<=m;   j++)
        {
            int w;
            scanf("%d",&w);
            addedge((i-1)*m+j,i*m+j,w);
            addedge(i*m+j,(i-1)*m+j,w);
        }
    }
    for(int i=1;    i<=n-1; i++)
    {
        for(int j=1;    j<=m-1; j++)
        {
            int w;
            scanf("%d",&w);
            addedge((i-1)*m+j,i*m+j+1,w);
            addedge(i*m+j+1,(i-1)*m+j,w);
        }
    }
    st=1;   ed=n*m;
    int ans=dinic();
    printf("%d\n",ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。