NOI 2010 海拔（最小割转最短路）

题意

https://www.lydsy.com/JudgeOnline/problem.php?id=2007

思路

首先可以发现一个结论，每个位置的海拔只有能是 \(0\) 和 \(1\) ，然后这道题就是求以人流量为边权的最小割。

直接用网络流求最小割似乎会T 。但这张图是个平面图，可以转化成它的对偶图求最短路，唯一要注意的一点是，这张无向图每条边正走和反走边权是不同的，于是转化对偶图的时候把每条边逆时针翻转 \(90\) 度即可，正确性讲不清楚，需要感性理解。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}

template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}

typedef long long ll;

const int N=505;

template<const int N,const int M,typename T>struct LinkedList

{

	int head[N],nxt[M],tot;T to[M];

	LinkedList(){clear();}

	T &operator [](const int x){return to[x];}

	void clear(){memset(head,-1,sizeof(head)),tot=0;}

	void add(int u,T v){to[tot]=v,nxt[tot]=head[u],head[u]=tot++;}

	#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])

};

template<typename T>struct Heap

{

	T a[4*N*N];int n;

	Heap(){clear();}

	void clear(){n=0;}

	bool empty(){return n==0;}

	T top(){return a[1];}

	void push(T val)

	{

		int x=++n;

		for(int y;(y=(x>>1));x=y)

		{

			if(val<a[y])a[x]=a[y];

			else break;

		}

		a[x]=val;

	}

	void pop()

	{

		int x=1;T val=a[n--];

		for(int y;(y=(x<<1))<=n;x=y)

		{

			if(y+1<=n&&a[y+1]<a[y])y++;

			if(a[y]<val)a[x]=a[y];

			else break;

		}

		a[x]=val;

	}

};

struct edge{int to,cost;};

struct node

{

	int at,path;

	bool operator <(const node &_)const{return path<_.path;}

};

LinkedList<N*N,4*N*N,edge>G;

Heap<node>H;

int dis[N*N];

int n,S,T;

inline int Hs(int x,int y)

{

	if(y<1||x>n)return S;

	if(y>n||x<1)return T;

	return (x-1)*n+y;

}

int dijkstra()

{

	FOR(i,1,T)dis[i]=1e9;

	H.clear();

	H.push((node){S,dis[S]=0});

	while(!H.empty())

	{

		node now=H.top();H.pop();

		int u=now.at;

		if(dis[u]<now.path)continue;

		EOR(i,G,u)

		{

			int v=G[i].to,w=G[i].cost;

			if(chk_min(dis[v],dis[u]+w))

				H.push((node){v,dis[v]});

		}

	}

	return dis[T];

}

int main()

{

	scanf("%d",&n);

	S=n*n+1,T=n*n+2;

	FOR(i,1,n+1)FOR(j,1,n)

	{

		int w;scanf("%d",&w);

		G.add(Hs(i,j),(edge){Hs(i-1,j),w});

	}

	FOR(i,1,n)FOR(j,0,n)

	{

		int w;scanf("%d",&w);

		G.add(Hs(i,j),(edge){Hs(i,j+1),w});

	}

	FOR(i,0,n)FOR(j,1,n)

	{

		int w;scanf("%d",&w);

		G.add(Hs(i,j),(edge){Hs(i+1,j),w});

	}

	FOR(i,1,n)FOR(j,1,n+1)

	{

		int w;scanf("%d",&w);

		G.add(Hs(i,j),(edge){Hs(i,j-1),w});

	}

	printf("%d\n",dijkstra());

	return 0;

}

巴特西

NOI 2010 海拔（最小割转最短路）

题意

思路

代码

最新文章

热门文章