NOI2006最大获利

2014年1月18日7,0394

题目描述 Description

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i 个通讯中转站需要的成本为 Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 Ai, Bi和 Ci：这些用户会使用中转站 Ai和中转站 Bi进行通讯，公司可以获益 Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

输入描述 Input Description

输入文件中第一行有两个正整数 N 和 M 。第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为 P1, P2, …, PN 。以下 M 行，第(i + 2)行的三个数 Ai, Bi和 Ci描述第 i 个用户群的信息。所有变量的含义可以参见题目描述。

输出描述 Output Description

你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

样例输入 Sample Input

5 5

1 2 3 4 5

1 2 3

2 3 4

1 3 3

1 4 2

4 5 3

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。

80%的数据中：N≤200，M≤1 000。

100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

代码

若a,b之间有一条收益为c的边，则新建一个点，点权为c，分别向a,b连边，a,b点权为他们的花费，这样转换成求最大权封闭子图，详见胡伯涛论文，s向正权点连边（容量为权值），负权点向t连边（容量为权值的绝对值），可以证明一个方案和一个割一一对应。

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x7fffffff
using namespace std;
struct data{
	int next,to,v;
}e[500001];
int n,m,ans;
int ne=1;
int q[60001],head[60001],h[60001];
void insert(int u,int v,int w)
{
	ne++;
	e[ne].to=v;
	e[ne].v=w;
	e[ne].next=head[u];
	head[u]=ne;
	ne++;
	e[ne].to=u;
	e[ne].next=head[v];
	head[v]=ne; 
}
bool bfs()
{
	int now,t=0,w=1,p,i;
	memset(h,-1,sizeof(h));
	q[t]=h[0]=0;
	while(t<w)
	{
		now=q[t];t++;
		i=head[now];
		while(i)
		{
			if(e[i].v&&h[e[i].to]<0)
			{
				q[w++]=e[i].to;
				h[e[i].to]=h[now]+1;
			}
			i=e[i].next;
		}
	}
	if(h[n+m+1]==-1)return 0;
	return 1;
}
int dfs(int x,int f)
{
	if(x==n+m+1)return f;
	int i=head[x];
	int w,used=0;
	while(i)
	{
		if(e[i].v&&h[e[i].to]==h[x]+1)
		{
			w=f-used;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;
			e[i^1].v+=w;
			used+=w;
			if(used==f)return f;
		}
		i=e[i].next;
	}
	if(!used)h[x]=-1;
	return used;
}
void dinic()
{
	while(bfs())ans+=dfs(0,INF);
}
int main()
{
	int sum=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		insert(0,i,a);
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		insert(a,n+i,INF);
		insert(b,n+i,INF);
		insert(n+i,n+m+1,c);
		sum+=c;
	}
	dinic();
	printf("%d",sum-ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define INF 0x7fffffff

using namespace std;

struct data{

int next,to,v;

}e[500001];

int n,m,ans;

int ne=1;

int q[60001],head[60001],h[60001];

void insert(int u,int v,int w)

{

ne++;

e[ne].to=v;

e[ne].v=w;

e[ne].next=head[u];

head[u]=ne;

ne++;

e[ne].to=u;

e[ne].next=head[v];

head[v]=ne;

}

bool bfs()

{

int now,t=0,w=1,p,i;

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

q[t]=h[0]=0;

while(t<w)

{

now=q[t];t++;

i=head[now];

while(i)

{

if(e[i].v&&h[e[i].to]<0)

{

q[w++]=e[i].to;

h[e[i].to]=h[now]+1;

}

i=e[i].next;

}

if(h[n+m+1]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==n+m+1)return f;

int i=head[x];

int w,used=0;

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic()

{

while(bfs())ans+=dfs(0,INF);

}

int main()

{

int sum=0;

scanf("%d%d",&n,&m);

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

{

int a;

scanf("%d",&a);

insert(0,i,a);

}

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

{

int a,b,c;

scanf("%d%d%d",&a,&b,&c);

insert(a,n+i,INF);

insert(b,n+i,INF);

insert(n+i,n+m+1,c);

sum+=c;

}

dinic();

printf("%d",sum-ans);

return 0;

}

« 「网络流24题」搭配飞行员(飞行员配对方案问题) 「CODEVS1022」覆盖 »

郭天成

黄学长，这题用最大密度子图怎么搞，就是胡伯涛论文里的O(MaxFlow(n,n+m))..并不会~

hzwer

不会

郭天成

黄学长别装弱

TigerTang

并不会用最大密度子图搞

hzwer.com _ Home | http://hzwer.com

NOI2006最大获利

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

代码

分类目录

热门文章

Myfriends

近期评论