BZOJ2007-[NOI2010]海拔(对偶图)

题目链接:BZOJ2007-NOI2010-海拔

题意:

给一个n×n的网格图,每条边双向通行。已知每条边两个方向的人流量,需要给每个点x设定一个海拔,左上角的海拔为0,右下角的海拔为1,对于x->y流量为w的边,代价为max(h,0) ×w,问最小代价。

题解:

显然,最优解中所有点的高度是0或者1,并且最优解中高度为0的点与左上角在同一连通块,高度为1的点与右下角在同一连通块中。所以我们只需要求这个图的最小割即可。考虑对偶图。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int MAXN=3e5+9;
const int MAXM=1e6+9;
int n;
struct Edge
{
    int v,w,nxt;
} edge[MAXM*2];
int fir[MAXN],cnt;
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*n+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()
{
    scanf("%d",&n);
    memset(fir,-1,sizeof(fir));
    for(int i=0; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(i==0)
                u=j,v=n*n+1;
            else    if(i==n)
                u=0,v=(i-1)*n+j;
            else
                u=i*n+j,v=(i-1)*n+j;
            addedge(u,v,w);
        }
    for(int i=1; i<=n; i++)
        for(int j=0; j<=n; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(j==0)
                u=0,v=(i-1)*n+j+1;
            else    if(j==n)
                u=i*n,v=n*n+1;
            else
                u=(i-1)*n+j,v=(i-1)*n+j+1;
            addedge(u,v,w);
        }
    for(int i=0; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(i==0)
                u=j,v=n*n+1;
            else    if(i==n)
                u=0,v=(i-1)*n+j;
            else
                u=i*n+j,v=(i-1)*n+j;
            addedge(v,u,w);
        }
     for(int i=1; i<=n; i++)
        for(int j=0; j<=n; j++)
        {
            int u,v,w;
            scanf("%d",&w);
            if(j==0)
                u=0,v=(i-1)*n+j+1;
            else    if(j==n)
                u=i*n,v=n*n+1;
            else
                u=(i-1)*n+j,v=(i-1)*n+j+1;
            addedge(v,u,w);
        }
    dijkstra(0);
    printf("%d\n",dis[n*n+1]);
    return 0;
}

发表留言

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