NOI2010 海拔

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2010 海拔

Date: Mon Sep 10 21:44:09 CST 2018

In Category: NoCategory

Description：

一个 $(n+1)\times (n+1)$ 的网格图，边有流量，左上角海拔为 $0$ ，右下角海拔为 $1$ ，当流量从低到高时会有流量 $\times$ 海拔差的代价，最小化整张图的代价。

$1\le n \le 500$

Solution：

首先可以猜结论：所有的海拔一定都是 $0$ 或 $1$ 。

然后就是把点划分为两个集合，最小化从第一个集合到第二个集合的边的边权和。

于是求最小割就好了。

Code(网络流)：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 510

struct edge

{

	int to,nxt,f;

}e[MAXN * MAXN * 4 * 2];

int edgenum = 0;

int lin[MAXN * MAXN];

inline void add(int a,int b,int f)

{

	if(f == 0)return;

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

inline int to(int i,int j){return (i - 1) * n + j;}

int s,t;

int ch[MAXN * MAXN];

#define INF 0x3f3f3f3f

#define rint register int 

inline bool BFS()

{

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		rint k = q.front();q.pop();

		for(rint i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return ch[t] != -1;

}

inline int flow(int k,int f)

{

	if(k == t)return f;

	rint r = 0;

	for(rint i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			rint l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

inline int dinic()

{

	rint ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

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

	n = read() + 1;

	s = 1,t = n * n;

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

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

			add(to(i,j),to(i,j + 1),read());

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

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

			add(to(i,j),to(i + 1,j),read());

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

		for(rint j = 2;j <= n;++j)

			add(to(i,j),to(i,j - 1),read());

	for(rint i = 2;i <= n;++i)

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

			add(to(i,j),to(i - 1,j),read());

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

	return 0;

}

Code(对偶图最短路)：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int n;

#define MAXN 510

int to(int i,int j){return (i - 1) * n + j;}

int s,t;

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN * 4];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{//cout << a << " " << b << " " << c << endl;

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

int d[MAXN * MAXN];

bool vis[MAXN * MAXN];

int dijkstra()

{

	memset(d,0x3f,sizeof(d));

	priority_queue< pair<int,int> > q;q.push(make_pair(0,s));

	d[s] = 0;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{//cout << k << " -> " << e[i].to << " " << e[i].v << endl;

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	return d[t];

}

int main()

{

	scanf("%d",&n);

	s = n * n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)add(to(1,i),t,read());

    for(int i = 2;i <= n;++i)for(int j = 1;j <= n;++j)add(to(i,j),to(i - 1,j),read());

    for(int i = 1;i <= n;++i)add(s,to(n,i),read());

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

	{

		add(s,to(i,1),read());

		for(int j = 2;j <= n;++j)add(to(i,j - 1),to(i,j),read());

		add(to(i,n),t,read());

	}

	for(int i = 1;i <= n;++i)add(t,to(1,i),read());

    for(int i = 2;i <= n;++i)for(int j = 1;j <= n;++j)add(to(i - 1,j),to(i,j),read());

    for(int i = 1;i <= n;++i)add(to(n,i),s,read());

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

	{

		add(to(i,1),s,read());

		for(int j = 2;j <= n;++j)add(to(i,j),to(i,j - 1),read());

		add(t,to(i,n),read());

	}

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

    return 0;

}

In tag: 图论-dinic

wjh15101051