首页 > 搜索 > DFS搜索 > HDU 4729-An Easy Problem for Elfness-分治-[解题报告]HOJ
2015
09-17

HDU 4729-An Easy Problem for Elfness-分治-[解题报告]HOJ

An Easy Problem for Elfness

问题描述 :

Pfctgeorge is totally a tall rich and handsome guy. He plans to build a huge water transmission network that covers the whole southwest China. To save the fund, there will be exactly one path between two cities.

Since the water every city provides and costs every day is different, he needs to transfer water from one particular city to another as much as possible in the next few days. However the pipes which connect the cities have a limited capacity for transmission. (Which means the water that transfer though the pipe should not exceed a particular amount) So he has to know the maximum water that the network can transfer in the next few days.

He thought it’s a maximum flow problem, so he invites an expert in this field, Elfness (Also known as Xinhang senior sister) to help him figure it out.

Unlike Pfctgeorge, Elfness quickly finds that this problem is much easier than a normal maximum flow problem, and is willing to help Pfctgeorge.

"Oh well, this problem is not a tough one. We can …"

Abruptly, Pfctgeorge’s iPhone rings, and … the ringtone is Mo Di Da Biao Ke.

"You can make that? Excellent! "Pfctgeorge hangs up his iPhone, and turns to Elfness.

"Here’s good news for you. A construction team told me that every pipe’s capacity can be extended for one day. And the price for extending one unit capacity varies from day to day. "

"Eh well, that’s a good news for you, not me. Now it’s rather like a minimum cost ow problem, right? But it’s still not a tough one, let me have a think. "

After a few seconds’ thought, Elfness comes up with a simple solution.

"Ok, we can solve it like… "

Abruptly, here comes Mo Di Da Biao Ke again.

"Seriously? You can build new pipes? Thank you very much. "

"OK, my dear Elfness, we got more good news. Another construction team said they can build one or more pipes between any two cities and their pipes are exactly like the original ones except that they only work for one day. And the capacity of the new pipes is only one, but they can be extended, too. Of course, their price to build a single pipe also varies in days. "

"You mean the new pipes can be extended too? Wow, things are getting more interesting. Give me a few minutes. "

Elfness takes out his new ultrabook which is awarded in VK cup and does some basic calculation.

"I get it. The problem can be solved …"

Mo Di Da Biao Ke again, but this time it’s from Elfness’s phone.

"As you see, I have to go out. But I know someone else who can also solve this; I’ll recommend this guy for you. "

And of course, that poor guy is YOU. Help Pfctgeorge solve his problem, and then the favorability about you from Elfness will raise a lot.

输入:

The first line has a number T (T <= 10) , indicating the number of test cases.

The first line of each test case is two integers N (1 <= N <= 100000) and M (1 <= M <= 100000), indicating the number of the city that the original network connects and the number of days when Pfctgeorge needs to know about the maximum water transmissions. Then next N – 1 lines each describe a pipe that connects two cities. The format will be like U, V , cap (1 <= U, V <= N and 0 <= cap < 10000), which means the ids of the two cities the pipe connects and the transmission limit of the pipe. As is said in description, the network that the cities and pipes form is a tree (an undirected acyclic graph).

Then next M lines of the test case describe the information about the next few days. The format is like S, T, K, A, B(0 <= K <= 2^31 – 1, 1 <= A, B <= 2^31 – 1). S means the source of the water while T means the sink. K means the total budget in the day. A means the cost for a construction team to build a new pipe and B means the cost for a construction team to extend the capacity of a pipe.

I am glad to list the information of building a new pipe and extending the capacity.

1. Pfctgeorge can build a new pipe between any two cities, no matter they have been directly connected or not. Pfctgeorge can build more than one new pipe between any two cities.
2. The capacity of the pipe that was newly built is one.
3. Pfctgeorge can extend the capacity of any existed pipe including the newly built one and the original one.
4. Each time you extend the capacity of one pipe, the capacity of that pipe increases one.
5. The cost of building a new pipe is A and the cost of extending a pipe is B.
6. You can take any constructions in any times and the only limit is to make sure the total costs not exceed the budget.
7. All the work that construction team does only lasts one single day.

输出:

The first line has a number T (T <= 10) , indicating the number of test cases.

The first line of each test case is two integers N (1 <= N <= 100000) and M (1 <= M <= 100000), indicating the number of the city that the original network connects and the number of days when Pfctgeorge needs to know about the maximum water transmissions. Then next N – 1 lines each describe a pipe that connects two cities. The format will be like U, V , cap (1 <= U, V <= N and 0 <= cap < 10000), which means the ids of the two cities the pipe connects and the transmission limit of the pipe. As is said in description, the network that the cities and pipes form is a tree (an undirected acyclic graph).

Then next M lines of the test case describe the information about the next few days. The format is like S, T, K, A, B(0 <= K <= 2^31 – 1, 1 <= A, B <= 2^31 – 1). S means the source of the water while T means the sink. K means the total budget in the day. A means the cost for a construction team to build a new pipe and B means the cost for a construction team to extend the capacity of a pipe.

I am glad to list the information of building a new pipe and extending the capacity.

1. Pfctgeorge can build a new pipe between any two cities, no matter they have been directly connected or not. Pfctgeorge can build more than one new pipe between any two cities.
2. The capacity of the pipe that was newly built is one.
3. Pfctgeorge can extend the capacity of any existed pipe including the newly built one and the original one.
4. Each time you extend the capacity of one pipe, the capacity of that pipe increases one.
5. The cost of building a new pipe is A and the cost of extending a pipe is B.
6. You can take any constructions in any times and the only limit is to make sure the total costs not exceed the budget.
7. All the work that construction team does only lasts one single day.

样例输入:

2
5 1
1 2 2
1 3 5
2 4 1
4 5 2
1 5 3 3 2
5 5
1 2 10
2 3 2
3 4 7
2 5 7
1 5 0 1 3
1 3 0 2 3
1 5 3 2 3
1 2 7 3 1
1 3 2 3 1

样例输出:

Case #1:
2
Case #2:
7
2
8
17
4
Hint
In the first sample case, you can extend the capacity of the pipe which connects city2 and city4 by one, or just build a new pipe between city2 and city4.

此题一看就知道是树链剖分,模板题!可怜我模板少抄个字母,在这两百多行的代码里找bug找了三个多小时啊!!!!

解题思路对于要求的x,y点,先可以求得不加任何操作的最大流量Pc1为建造一个路的话费,c2为增加一个容量的花费,如果c1<=c2,那么结果就为P+k/c1

否则,如果先建一条路,那么最大的流量是M=P+1+(k-c1)/c2,如果不新建路只加边呢?那就可以二分求得最大的结果为了节省时间,可以对整体进行最小值为M的二分结果。

下面是我的代码,不是很简单,但是各个函数还算清晰了。。。。

#pragma comment(linker,"/STACK:124000000,124000000")
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<climits>
#include<map>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repf(i,n,m) for(int i=(n); i<=(m); ++i)
#define repd(i,n,m) for(int i=(n); i>=(m); --i) 
#define ll __int64
#define arc(a) ((a)*(a))
#define inf 100000
#define exp 0.000001
#define N  200005

class match{
public:
	int n,m,len,topw;
	int fa[N],size[N],son[N],w[N],top[N],dep[N];
	int pre[N],lit[N];
	int value[N];
	int p[N];
	int cont;
	struct node{ int y,pre,v;};
	node a[N];
	struct no{int l,r,Min;};
	no aa[N*4];
	void init()
	{
		len=0; topw=1;value[1]=0;
		memset(pre,-1,sizeof(pre));
		memset(son,-1,sizeof(son));
	}
	void addpage(int x,int y,int z)
	{
		a[len].pre=pre[x];
		a[len].v=z;
		a[len].y=y;
		pre[x]=len++;
	}
	void dfs(int s,int faa,int h)
	{
		dep[s]=h;
		size[s]=1;
		int Max=0,sign;
		for(int i=pre[s]; i!=-1; i=a[i].pre)
		{
			int y=a[i].y;
			if(y==faa) continue;
			fa[y]=s;
			value[y]=a[i].v;//jilu shangyi ge 
			dfs(y,s,h+1);
			if(size[y]>Max) Max=size[y],sign=y;
			size[s]+=size[y];
		}
		if(Max!=0) son[s]=sign;
	}
	void dfs2(int s,int faa,int tp)
	{
		p[topw]=s;
		w[s]=topw++; top[s]=tp;
		if(son[s]!=-1) dfs2(son[s],s,tp);
		for(int i=pre[s]; i!=-1; i=a[i].pre)
		{
			int y=a[i].y;
			if(y==faa || y==son[s]) continue;
			dfs2(y,s,y);
		}
		lit[s]=topw-1;
	}
	void bulidtree(int s,int l,int r)
	{
		 aa[s].l=l, aa[s].r=r;
		if(l==r) 
		{
			aa[s].Min=value[p[l]];
			return;
		}
		int mid=(l+r)/2;
		bulidtree(2*s,l,mid);
		bulidtree(2*s+1,mid+1,r);
		aa[s].Min=min(aa[2*s].Min,aa[2*s+1].Min);
	}
	int refresh(int s,int l,int r)
	{
		if(aa[s].l>=l && aa[s].r<=r)
			return aa[s].Min;
		int mid=(aa[s].l+aa[s].r)/2;
		if(r<=mid)
			return refresh(2*s,l,r);
		else if(l>mid) 
			return refresh(2*s+1,l,r);
		else return min(refresh(2*s,l,r),refresh(2*s+1,l,r));
	}
	int deal(int s,int x,int y)
	{
        int fx=top[x],fy=top[y];
		int Min=INT_MAX;
		while(fx!=fy)
		{
			if(dep[fx]>dep[fy])
				swap(fx,fy),swap(x,y);
            Min=min(Min,refresh(1,w[fy],w[y]));
			y=fa[fy],fy=top[y];
		}
		if(dep[x]>dep[y])
			swap(x,y);
		if(x!=y)
		Min=min(Min,refresh(1,w[x]+1,w[y]));
		if(Min==INT_MAX)
			Min=9999;
		return Min;
	}
	bool True(int s,int l,int r,ll mid)
	{
//		cout<<s<<" "<<l<<" "<<r<<" "<<mid<<" "<<cont<<endl;
		if(aa[s].l>=l && aa[s].r<=r && aa[s].Min>=mid)
			return true;
		if(aa[s].l==aa[s].r)
		{
			if(aa[s].Min>=mid) return true;
			cont-=(mid-aa[s].Min);
			if(cont<0) return false;
			return true;
		}
		int mi=(aa[s].l+aa[s].r)/2;
		if(r<=mi) return True(2*s,l,r,mid);
		else if(l>mi) return True(2*s+1,l,r,mid);
		if(True(2*s,l,r,mid) && True(2*s+1,l,r,mid))
			return true;
		return false;
	}
	bool fun(int s,int x,int y,ll mid)
	{
		int fx=top[x],fy=top[y];
		while(fx!=fy)
		{
			if(dep[fx]>dep[fy])
				swap(fx,fy),swap(x,y);
			if(!True(1,w[fy],w[y],mid))
				return false;
			y=fa[fy]; fy=top[y];
		}
		if(dep[x]>dep[y]) swap(x,y);
		if(x!=y)
		if(!True(1,w[x]+1,w[y],mid))
			return false;
		return true;
	}
};
match sa;
int n,m;

int main()
{
//	freopen("in","r",stdin);
	int test;
	scanf("%d",&test);
	repf(ror,1,test)
	{
		scanf("%d%d",&n,&m);
		sa.n=n;
		sa.init();
		int x,y,z,k,c1,c2;
		rep(i,n-1)
		{
			scanf("%d%d%d",&x,&y,&z);
			sa.addpage(x,y,z);
			sa.addpage(y,x,z);
		}
		sa.dfs(1,-1,1);
		sa.dfs2(1,-1,1);
		sa.bulidtree(1,1,n);
		printf("Case #%d:\n",ror);
		repf(i,1,m)
		{
			scanf("%d%d%d%d%d",&x,&y,&k,&c1,&c2);
			ll rr=sa.deal(1,x,y);
            ll an=rr+k/c1;
			ll ans;
			if(c1<=c2)
				ans=an;
			else
			{
			if(k>=c1) an=max(an,rr+1+(k-c1)/c2);
			ll l=an,r=10000+max(k/c2,k/c1);
			ans=an;
			int cont=k/c2;
			sa.cont=cont;
			while(l<=r)
			{
				ll mid=(l+r)/2;
				sa.cont=cont;
                if(sa.fun(1,x,y,mid))
					ans=mid,l=mid+1;
				else r=mid-1;
			}
			}
	    	printf("%I64d\n",ans);
		//	cout<<ans<<endl;
		}
	}
   return 0;
}
  

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xuezhongfenfei/article/details/12716539