bzoj 4289 Tax

Posted on | Views:

构造建图 + 最短路.

先将无向边拆成两条有向边,于是可以将原图中的每条有向边看成一个点,建一个新图.

枚举中继点 $x$ ,则对 $a\to x,x\to b$ 这两条边在新图中连上对应有向边,权值为两者最大值.

在新图中建立源汇点 $S,T$ ,从 $S$ 向所有在原图中以 $1$ 为起点的边连边,从所有在原图中以 $n$ 为终点的边向 $T$ 连边,权值均为原来的权值,那么答案就是新图中 $S\to T$ 的最短路.

但这样边数可以被菊花图这样的东西卡到 $O(m^2)$ 去,需要利用差分的思想优化连边.

对于每个点 $u$ ,将所有以它为起点的边按照权值从小到大排序,对于相邻的两条边 $x,y$ ,假设 $val_x<val_y$ ,就在新图中从 $x$ 向 $y$ 连权值为 $val_y-val_x$ 的边,从 $y$ 向 $x$ 连权值为 $0$ 的边, $S,T$ 相关的边连法不变.

这样连边边数就是 $O(m)$ 了,在新图上跑 $Dijkstra$ 求出最短路.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int N=1e5+10,M=4e5+10;
const int MAXM=2e6+10;
int n,m;
typedef pair<ll,int> pli;
priority_queue<pli> q;
const ll inf=1e18;
struct Graph
{
	int ecnt,head[MAXM],to[MAXM],nx[MAXM],vis[MAXM];
	ll val[MAXM],dis[MAXM];
	void addedge(int u,int v,ll w)
	{
		++ecnt;
		to[ecnt]=v;
		nx[ecnt]=head[u];
		val[ecnt]=w;
		head[u]=ecnt;
	}
	Graph(){ecnt=0;memset(head,0,sizeof head);}
	ll Dijkstra(int S,int T,int tot)
	{
		for(int i=1;i<=tot;++i)
			vis[i]=0,dis[i]=inf;
		dis[S]=0;
		q.push(make_pair(-dis[S],S));
		while(!q.empty())
		{
			int u=(q.top()).second;
			q.pop();
			if(vis[u])
				continue;
			vis[u]=1;
			for(int i=head[u];i;i=nx[i])
			{
				int v=to[i];
				if(dis[v]-val[i]>dis[u])
				{
					dis[v]=dis[u]+val[i];
					q.push(make_pair(-dis[v],v));
				}
			}
		}
		return dis[T];
	}
}G;
int ecnt,head[N],to[M],nx[M];
ll val[M];
void addedge(int u,int v,ll w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
bool cmp(int x,int y)
{
	return val[x]<val[y];
}
int S,T,tmp[MAXM],cnt;
void BuildGraph()
{
	S=ecnt+1,T=ecnt+2;
	for(int i=1;i<=ecnt;i+=2)
	{
		G.addedge(i,i+1,val[i]);
		G.addedge(i+1,i,val[i]);
	}
	for(int u=1;u<=n;++u)
	{
		cnt=0;
		for(int i=head[u];i;i=nx[i])
			tmp[++cnt]=i;
		sort(tmp+1,tmp+1+cnt,cmp);
		for(int i=1;i<cnt;++i)
		{
			int x=tmp[i],y=tmp[i+1];
			G.addedge(x,y,val[v]-val[u]);
			G.addedge(y,x,0);
		}
	}
	for(int i=head[1];i;i=nx[i])
		G.addedge(S,i,val[i]);
	for(int i=head[n];i;i=nx[i])
		G.addedge((i&1)?i+1:i-1,T,val[i]);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		ll w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	BuildGraph();
	printf("%lld\n",G.Dijkstra(S,T,T));
	return 0;
}