洛谷2046 NOI2010海拔

QwQ题目太长这里就不复制了

这个题...算是个比较经典的平面图最小割变成对偶图的最短路了QwQ

首先考虑最小割应该怎么做。

有一个性质，就是每个点的海拔要么是1，要么是0

QwQ不过这个我不会证明啊

那么既然知道了这个性质，我们对于地图上的每个点，实际上就是划分成两个集合，一个是\(1\)，一个是\(0\)

那么直接最小割就行了

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

inline int read()

{

   int x=0,f=1;char ch=getchar();

   while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}

   while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

   return x*f;

}

const int maxn = 110*110;

const int maxm = 1e6+1e2;

const int inf = 1e9;

int point[maxn];

int nxt[maxm],to[maxm],val[maxm];

int cnt=1;

int h[maxn];

queue<int> q;

int n,m;

int s,t;

void addedge(int x,int y,int w)

{

    nxt[++cnt]=point[x];

    to[cnt]=y;

    val[cnt]=w;

    point[x]=cnt;

}

void insert(int x,int y,int w)

{

    addedge(x,y,w);

    addedge(y,x,0);

}

bool bfs(int s)

{

    memset(h,-1,sizeof(h));

    h[s]=0;

    q.push(s);

    while (!q.empty())

    {

        int x  = q.front();

        q.pop();

        for (int i=point[x];i;i=nxt[i])

        {

            int p = to[i];

            if (val[i]>0 && h[p]==-1)

            {

                h[p]=h[x]+1;

                q.push(p);

            }

        }

    }

    if (h[t]==-1) return false;

    else return true;

}

int dfs(int x,int low)

{

    if (x==t || low==0) return low;

    int totflow=0;

    for (int i=point[x];i;i=nxt[i])

    {

        int p = to[i];

        if (val[i]>0 && h[p]==h[x]+1)

        {

            int tmp = dfs(p,min(low,val[i]));

            low-=tmp;

            totflow+=tmp;

            val[i]-=tmp;

            val[i^1]+=tmp;

            if (low==0) return totflow;

        }

    }

    if (low>0) h[x]=-1;

    return totflow;

}

int dinic()

{

    int ans=0;

    while (bfs(s))

    {

        ans=ans+dfs(s,inf);

    }

    return ans;

}

int main()

{

  n=read();

  n++;

  s=1;

  t=n*n;

  for (int i=1;i<=n;i++)

  {

    //int now =(i-1)*n;

    for (int j=1;j<n;j++)

    {

    	int x = read();

    	//cout<<x<<endl;

        insert((i-1)*n+j,(i-1)*n+j+1,x);

        //cout<<(i-1)*n+j<<" "<<(i-1)*n+j+1<<endl;

    }

  }

  for (int i=1;i<n;i++)

    for (int j=1;j<=n;j++)

    {

    	int x = read();

    	insert((i-1)*n+j,i*n+j,x);

    }

  for (int i=1;i<=n;i++)

  {

    for (int j=1;j<n;j++)

    {

    	int x = read();

        insert((i-1)*n+j+1,(i-1)*n+j,x);

    }

  }

  for (int i=1;i<n;i++)

    for (int j=1;j<=n;j++)

    {

    	int x = read();

    	insert(i*n+j,(i-1)*n+j,x);

    }

  cout<<dinic()<<endl;

  return 0;

}

不过这个最小割的复杂度是爆炸的，显然没法通过这个题，那么我们这时候就需要用到一个很关键的性质了

平面图最小割等于对偶图的最短路

那么什么是对偶图呢？

简单来说，就是把原图的每个封闭面，看成一个点，然后原图的每一种割，对应着新图\(s到t\)的一条路径

但是QwQ这里先留跟个坑，就是关于边的方向的问题....这里还不是很理解呢

转化成新图，建好图之后，直接从\(S\)开始跑最短路，\(dis[t]\)就是答案

一般原图的st和新图的st成对角线的关系

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define pa pair<long long,long long>

#include<queue>

using namespace std;

inline long long read()

{

   long long x=0,f=1;char ch=getchar();

   while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}

   while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

   return x*f;

}

const int maxn = 510;

const int N = maxn*maxn;

const int maxm = 2e6+1e2;

int a[maxn][maxn][maxn];

int point[N],nxt[maxm],to[maxm];

int cnt;

int vis[N];

int n,m;

long long dis[N],val[maxm];

priority_queue<pa,vector<pa>,greater<pa> > q;

int s,t;

void addedge(int x,int y,long long w){

   nxt[++cnt]=point[x];

   to[cnt]=y;

   val[cnt]=w;

   point[x]=cnt;

}

void splay(int s)

{

    memset(vis,0,sizeof(vis));

    memset(dis,127/3,sizeof(dis));

    //cout<<dis[1]<<endl;

    dis[s]=0;

    q.push(make_pair(0,s));

    while (!q.empty())

    {

        //cout<<1<<endl;

        int x = q.top().second;

        q.pop();

        //cout<<x<<endl;

        if (vis[x]) continue;

        vis[x]=1;

        for (int i=point[x];i;i=nxt[i])

        {

            int p = to[i];

            if (dis[p]>dis[x]+val[i])

            {

                dis[p]=dis[x]+val[i];

                //cout<<dis[p]<<" "<<p<<endl;

                q.push(make_pair(dis[p],p));

                //cout<<endl;

            }

        }

    }

}

inline int getnum(int x,int y)

{

    if (x==0 || y==n) return t;

    if (x==n || y==0 ) return s;

    return (x-1)*(n-1)+y;

}

int main()

{

  n=read();

  n++;

  s=N-6;

  t=s+1;

  for (int i=1;i<=n;i++)

    for (int j=1;j<n;j++)

    {

    	long long x=read();

    	addedge(getnum(i,j),getnum(i-1,j),x);

    	//cout<<getnum(i,j)<<" "<<getnum(i-1,j)<<endl;

    }

  for (int i=1;i<n;i++)

    for (int j=1;j<=n;j++)

    {

    	long long x = read();

    	addedge(getnum(i,j-1),getnum(i,j),x);

        //cout<<getnum(i,j-1)<<" "<<getnum(i,j)<<endl;

        //cout<<x<<endl;

    }

  for (int i=1;i<=n;i++)

    for (int j=1;j<n;j++)

    {

    	long long x=read();

    	addedge(getnum(i-1,j),getnum(i,j),x);

    }

   for (int i=1;i<n;i++)

    for (int j=1;j<=n;j++)

    {

    	long long x = read();

    	addedge(getnum(i,j),getnum(i,j-1),x);

    }

    splay(s);

    cout<<dis[t];

  return 0;

}

巴特西

洛谷2046 NOI2010海拔

最新文章

热门文章