首页 > ACM题库 > HDU-杭电 > HDU 3618-Good Plan[解题报告]HOJ
2014
11-29

HDU 3618-Good Plan[解题报告]HOJ

Good Plan

问题描述 :

FJ has two same house for rant. Now he has n (1 ≤ n ≤ 1000) piece of order, the orders are given in the form:

s t v

means that someone want to rant a hours from the day s to t paying v yuan totally (including the day s and t, 0 ≤ s ≤ t ≤ 400, 0 ≤ v ≤ 100,0000).

A hours can be only rant to one person, and FJ should either accept an order totally or reject it.

输入:

The first line of input file is a single integer T – The number of test cases. For each test case, the first line is a single integer n then there n lines, each line gives an order.

输出:

The first line of input file is a single integer T – The number of test cases. For each test case, the first line is a single integer n then there n lines, each line gives an order.

样例输入:

3
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640

样例输出:

30
25500
38595

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 409
int S,T;
struct edge
{
	int v,flow,cost;
	edge *next,*opp;
}A[500009],*adj[maxn];
#define NEW() &A[++ANS]
int ANS;
inline void addedge(int u,int v,int flow,int cost)
{
	edge *ptr=NEW();
	ptr->v=v;
	ptr->flow=flow;
	ptr->cost=cost;
	ptr->next=adj[u]->next;
	ptr->opp=&A[ANS^1];
	adj[u]->next=ptr;
}
#define Inf 1000000000
int q[1000009],d[maxn];
bool vis[maxn];
edge *pre[maxn];
bool spfa()
{
	memset(vis,0,sizeof(vis));
	for(int i=S;i<=T;i++)
		d[i]=Inf;
	int head=0,tail=1,u,v;
	q[0]=S;
	d[S]=0;
	while(head!=tail)
	{
		u=q[head++];
		vis[u]=false;
		for(edge *ptr=adj[u]->next;ptr!=NULL;ptr=ptr->next)
		{
			v=ptr->v;
			if(ptr->flow&&d[v]>d[u]+ptr->cost)
			{
				d[v]=d[u]+ptr->cost;
				pre[v]=ptr;
				if(!vis[v])
				{
					vis[v]=true;
					q[tail++]=v;
				}
			}
		}
	}
	return d[T]!=Inf;
}
int solve()
{
	int mincost=0;
	while(spfa())
	{
		edge *ptr;
		int low=Inf;
		for(int i=T;i!=S;)
		{
			ptr=pre[i];
			low=min(low,ptr->flow);
			i=ptr->opp->v;
		}
		for(int i=T;i!=S;)
		{
			ptr=pre[i];
			ptr->flow-=low;
			ptr->opp->flow+=low;
			i=ptr->opp->v;
		}
		if(d[T]>=0)
			break;
		mincost+=low*d[T];
	}
	return mincost;
}
int main()
{
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		int s,t,v,n;
		S=0;	
		scanf("%d",&n);
		
		ANS=-1;
		for(int i=0;i<406;i++)
		{
			adj[i]=new edge();
			adj[i]->next=NULL;
		}
		for(int k=1;k<=n;k++)
		{
			scanf("%d%d%d",&s,&t,&v);
			s++;
			t++;
			addedge(s,t+1,1,-v);
			addedge(t+1,s,0,v);
			T=max(T,t+1);
		}
		for(int i=S;i<T;i++)
		{
			addedge(i,i+1,2,0);
			addedge(i+1,i,0,0);
		}
		printf("%d\n",-solve());
	}
	return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。