首页 > ACM题库 > HDU-杭电 > hdu 2715 Herd Sums-网络流-[解题报告]C++
2014
02-14

hdu 2715 Herd Sums-网络流-[解题报告]C++

Herd Sums

问题描述 :

The cows in farmer John’s herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N.

Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10.

Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.

输入:

* Line 1: A single integer: N

输出:

* Line 1: A single integer: N

样例输入:

15

样例输出:

4

跟方格取数有点类似,只是有了高度的限制。

建模方法:

1将每个格子i拆成两个点i,i,加边(i’,i”,1,-Vi)
->
保证单元内的宝物只能取一次

2、加边(i’,i”,inf,0),(s,i’,k,0) ->
保证一开始可以从任意高度出发。(注意源点s到i’的容量不能为inf)

3、对相邻的四个格子j,若Hi > Hj则加边(i”,j’,inf,0) ->
保证可以向相邻的格子移动。

4、若格子i在边界上则加边(i”,t,inf,0) ->
在边界时结束旅行。

最后需要限制增广次数小于等于k,做一次最小费用流即可。

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50 + 10;
const int maxpoint = 10000;
const int maxm = 200000;
struct Edge
{
	int d,c,w,pos;
	int next;
}E[maxm];
int w[maxn][maxn],h[maxn][maxn];
int pre[maxpoint],dis[maxpoint],head[maxpoint];
int que[maxm];
bool vis[maxpoint];
int NE,T;
int n,m,k;
int s,t;
void init()
{
	freopen("hoj2715.in","r",stdin);
	freopen("hoj2715.out","w",stdout);
}

void insert(int u,int v,int c,int w)
{
	E[NE].c = c;E[NE].pos = v;E[NE].d = u;E[NE].w = w;
	E[NE].next = head[u];head[u] = NE++;
    E[NE].c = 0;E[NE].pos = u;E[NE].d = v;E[NE].w = -w;
	E[NE].next = head[v];head[v] = NE++;	
}

void build_map()
{
	int tmp = n * n;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			insert((i - 1) * n + j,((i - 1) * n + j) + tmp,1,-w[i][j]);
			insert((i - 1) * n + j,((i - 1) * n + j) + tmp,inf,0);
			insert(s,(i - 1) * n + j,k,0);
			if(i > 1 && h[i][j] > h[i-1][j])insert(((i - 1) * n + j) + tmp,(i - 2) * n + j,inf,0);
			if(i < n && h[i][j] > h[i+1][j])insert(((i - 1) * n + j) + tmp,i * n + j,inf,0);
			if(j > 1 && h[i][j] > h[i][j-1])insert(((i - 1) * n + j) + tmp,(i - 1) * n + j - 1,inf,0);
			if(j < n && h[i][j] > h[i][j+1])insert(((i - 1) * n + j) + tmp,(i - 1) * n + j + 1,inf,0);
			if(i == 1 || i == n || j == 1 || j == n)insert(((i - 1) * n + j) + tmp,t,inf,0);
		}
	}
}

int spfa()
{
	int l,r;
	memset(pre,-1,sizeof(pre));
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	l = 0,r = 0;
	que[r++] = s;
	vis[s] = true;
	while(l < r)
	{
		int u = que[l++];l %= maxm;
		vis[u] = false;
		for(int i = head[u];i != -1;i = E[i].next)
		{
			int v = E[i].pos;
			if(E[i].c && dis[u] + E[i].w < dis[v])
			{
				dis[v] = dis[u] + E[i].w;
				pre[v] = i;
				if(!vis[v])
				{
					vis[v] = true;
					que[r++] = v;r %= maxm;
				}
			}
		}
	}
	if(dis[t] == inf)return false;
	else return true;
}

int MCMF()
{
	int ret = 0,flow = 0,cnt = 0;
	while(spfa())
	{
		int u = t;
		int min = inf;
		while(u != s)
		{
			if(E[pre[u]].c < min)min = E[pre[u]].c;
			u = E[pre[u]].d;
		}
		flow += min;
		u = t;
		while(u != s)
		{
			E[pre[u]].c -= min;
			E[pre[u]^1].c += min;
			u = E[pre[u]].d;
		}
		ret += dis[t];
		cnt++;
		if(cnt == k)break;
	}
	return ret;
}

void solve()
{
	memset(E,0,sizeof(E));
	memset(head,-1,sizeof(head));
	NE = 0,s = 0,t = n * n * 2 + 1;
	build_map();
	printf("%d\n",-MCMF());
}

void readdata()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(w,0,sizeof(w));
		memset(h,0,sizeof(h));
		scanf("%d%d",&n,&k);
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				scanf("%d",&w[i][j]);
			}
		}
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				scanf("%d",&h[i][j]);
			}
		}
		solve();
	}
}

int main()
{
	init();
	readdata();
	return 0;
}

解题转自:http://blog.csdn.net/njlcazl/article/details/8733539


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?