「BZOJ3206」[Apio2013] 道路费用

2015年4月27日6,6480

Description

Input

你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai，bi和c i，表示有一条在a i和b i之间，费用为c i的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j 前往城镇 1的人数。
输入也满足以下约束条件。

 1 ≤ N ≤ 100000；
 1 ≤ K ≤ 20；

 1 ≤ M ≤ 300000；

 对每个i和j，1 ≤ ci, pj ≤ 10^6；

Output

你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。

Sample Input

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

Sample Output

400

HINT

在样例中， Mr. Greedy应该将新道路(1,3)的费用设置为 5分钱。在这个费用下，他可以选择道路(3,5)，(1,2)，(2,4)和(1,3)来最小化总费用，这个费用为 14。从城镇 3出发的 30个人和从城镇 5出发的 50个人将经过新道路前往城镇 1，因此他可以获得为(30+50)_5=400 分钱的最好收入。

如果我们这样做，将新道路(1,3)的费用设置为 10分钱。根据传统的限制，Mr. Greedy必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合。因此，在嘉年华的过程中道路(1,3)将没有任何收入。

题解

说起来好麻烦。。应该题解到处都是吧

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,m,K,top,cnt,st;
int fa[100005],fa2[100005],p[100005];
struct edge{
	int u,v,w;
}e[300005],ne[25],q[300005];
struct data{
	int to,next;
}ed[50];
int po[25],dep[100005],last[100005],mn[100005];
ll val[100005],sum[100005];
bool mark[300005];
void insert(int u,int v)
{
	ed[++cnt]=(data){v,last[u]};last[u]=cnt;
	ed[++cnt]=(data){u,last[v]};last[v]=cnt;
}
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int find2(int x)
{
	return x==fa2[x]?x:fa2[x]=find2(fa2[x]);
}
bool operator<(edge a,edge b)
{
	return a.w<b.w;
}
void dp(int x)
{
	sum[x]=val[x];
	for(int i=last[x];i;i=ed[i].next)
		if(ed[i].to!=fa2[x])
		{
			dep[ed[i].to]=dep[x]+1;
			fa2[ed[i].to]=x;
			dp(ed[i].to);
			sum[x]+=sum[ed[i].to];
		}
}
void solve()
{
	cnt=0;
	for(int i=1;i<=K+1;i++)
	{
		int p=po[i];
		last[p]=fa2[p]=0;
		fa[p]=p;mn[p]=inf;
	}
	for(int i=1;i<=K;i++)
		if(mark[i])
		{
			int x=find(ne[i].u),y=find(ne[i].v);
			if(x==y)return;
			fa[x]=y;
			insert(ne[i].u,ne[i].v);
        }
	for(int i=1;i<=K;i++)
	{
		int x=find(q[i].u),y=find(q[i].v);
		if(x!=y)fa[x]=y,insert(q[i].u,q[i].v);
	}
	dp(st);
	for(int i=1;i<=K;i++)
	{
		int u=q[i].u,v=q[i].v;
		if(dep[u]>dep[v])swap(u,v);
		while(dep[v]!=dep[u])mn[v]=min(mn[v],q[i].w),v=fa2[v];
		while(u!=v)
		{
            mn[v]=min(mn[v],q[i].w);
            mn[u]=min(mn[u],q[i].w);
            u=fa2[u];v=fa2[v];
        }
	}
	ll inc=0;
	for(int i=1;i<=K;i++)
		if(mark[i])
		{
			int u=ne[i].u,v=ne[i].v;
			if(dep[u]>dep[v])swap(u,v);
			inc+=mn[v]*sum[v];
		}
	ans=max(inc,ans);
}
void dfs(int x)
{
	if(x==K+1)
	{
		solve();return;
	}
	mark[x]=0;dfs(x+1);
	mark[x]=1;dfs(x+1);
}
int main()
{
	n=read();m=read();K=read();
	for(int i=1;i<=m;i++)
		e[i].u=read(),e[i].v=read(),e[i].w=read();
	sort(e+1,e+m+1);
	for(int i=1;i<=K;i++)
		ne[i].u=read(),ne[i].v=read();
	for(int i=1;i<=n;i++)p[i]=read();
	for(int i=1;i<=n;i++)fa[i]=fa2[i]=i;
    for(int i=1;i<=K;i++)
		fa[find(ne[i].u)]=find(ne[i].v);
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v;
		if(find(u)!=find(v))
		{
			fa[find(u)]=fa[find(v)];
			fa2[find2(u)]=fa2[find2(v)];
		}
	}
	st=find2(1);
	for(int i=1;i<=n;i++)
	{
		val[find2(i)]+=p[i];
		if(find2(i)==i)po[++po[0]]=i;
	}
	for(int i=1;i<=K;i++)
		ne[i].u=find2(ne[i].u),ne[i].v=find2(ne[i].v);
	for(int i=1;i<=m;i++)
		e[i].u=find2(e[i].u),e[i].v=find2(e[i].v);
	for(int i=1;i<=m;i++)
	{
		int p=find2(e[i].u),q=find2(e[i].v);
		if(p!=q)mark[i]=1,fa2[p]=q;
	}
	for(int i=1;i<=m;i++)
		if(mark[i])q[++top]=e[i];
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n,m,K,top,cnt,st;

int fa[100005],fa2[100005],p[100005];

struct edge{

int u,v,w;

}e[300005],ne[25],q[300005];

struct data{

int to,next;

}ed[50];

int po[25],dep[100005],last[100005],mn[100005];

ll val[100005],sum[100005];

bool mark[300005];

void insert(int u,int v)

{

ed[++cnt]=(data){v,last[u]};last[u]=cnt;

ed[++cnt]=(data){u,last[v]};last[v]=cnt;

}

int find(int x)

{

return x==fa[x]?x:fa[x]=find(fa[x]);

}

int find2(int x)

{

return x==fa2[x]?x:fa2[x]=find2(fa2[x]);

}

bool operator<(edge a,edge b)

{

return a.w<b.w;

}

void dp(int x)

{

sum[x]=val[x];

for(int i=last[x];i;i=ed[i].next)

if(ed[i].to!=fa2[x])

{

dep[ed[i].to]=dep[x]+1;

fa2[ed[i].to]=x;

dp(ed[i].to);

sum[x]+=sum[ed[i].to];

}

void solve()

{

cnt=0;

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

{

int p=po[i];

last[p]=fa2[p]=0;

fa[p]=p;mn[p]=inf;

}

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

if(mark[i])

{

int x=find(ne[i].u),y=find(ne[i].v);

if(x==y)return;

fa[x]=y;

insert(ne[i].u,ne[i].v);

}

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

{

int x=find(q[i].u),y=find(q[i].v);

if(x!=y)fa[x]=y,insert(q[i].u,q[i].v);

}

dp(st);

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

{

int u=q[i].u,v=q[i].v;

if(dep[u]>dep[v])swap(u,v);

while(dep[v]!=dep[u])mn[v]=min(mn[v],q[i].w),v=fa2[v];

while(u!=v)

{

mn[v]=min(mn[v],q[i].w);

mn[u]=min(mn[u],q[i].w);

u=fa2[u];v=fa2[v];

}

ll inc=0;

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

if(mark[i])

{

int u=ne[i].u,v=ne[i].v;

if(dep[u]>dep[v])swap(u,v);

inc+=mn[v]*sum[v];

}

ans=max(inc,ans);

}

void dfs(int x)

{

if(x==K+1)

{

solve();return;

}

mark[x]=0;dfs(x+1);

mark[x]=1;dfs(x+1);

}

int main()

{

n=read();m=read();K=read();

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

e[i].u=read(),e[i].v=read(),e[i].w=read();

sort(e+1,e+m+1);

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

ne[i].u=read(),ne[i].v=read();

for(int i=1;i<=n;i++)p[i]=read();

for(int i=1;i<=n;i++)fa[i]=fa2[i]=i;

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

fa[find(ne[i].u)]=find(ne[i].v);

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

{

int u=e[i].u,v=e[i].v;

if(find(u)!=find(v))

{

fa[find(u)]=fa[find(v)];

fa2[find2(u)]=fa2[find2(v)];

}

st=find2(1);

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

{

val[find2(i)]+=p[i];

if(find2(i)==i)po[++po[0]]=i;

}

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

ne[i].u=find2(ne[i].u),ne[i].v=find2(ne[i].v);

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

e[i].u=find2(e[i].u),e[i].v=find2(e[i].v);

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

{

int p=find2(e[i].u),q=find2(e[i].v);

if(p!=q)mark[i]=1,fa2[p]=q;

}

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

if(mark[i])q[++top]=e[i];

dfs(1);

printf("%lld\n",ans);

return 0;

}

« 「BZOJ1478」Sgu282 Isomorphism 「BZOJ1194」[HNOI2006] 潘多拉的盒子 »

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

「BZOJ3206」[Apio2013] 道路费用

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论