营救皮卡丘[ZJOI2011]

发表于 分类于 ，

题目

链接

题解

我们考虑一个人从某个点 $i$ 到另外一个比该点编号大的点 $j$ 的情况。

但是这时候我们不能经过编号大于 $i$ 和 $j$ ，因此需预处理出不经过 编号比 $i,j$ 大的点，从 $i$ 到 $j$ 的最短路。这个用Floyd即可实现。

这样做就保证了答案的合法性。

现在问题变成有 $k$ 条从 $0$ 号点的路径，除了该点外不经过重复的点，边有边权及费用，每个点经过一次的模型。

这就类似于最小路径覆盖了。

对于每个非 $0$ 点拆点。

首先是 $(s,0,k,0)$，表示最多不超过 $k$ 个人在上面走。

然后是 $(i’,t,1,0),(s,i,1,0)$，代表每个点至少经过一遍，经过以后可以继续走。

接着对于 $i<j$ 的情况，连边 $(i,j’,1,dis_{i,j})$，表示从 $i$ 走到 $j$ 的最小费用为 $dis_{i,j}$。

跑最小费用最大流即可。

程序

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
//#include <unordered_set>
//#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
#define bit(x,i) (((x)>>(i))&1)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int M=100000;
const int N=310;
const ll inf=1e18;
namespace Graph{
	int n,m,s,t;
	int ver[M],val[M],cost[M],ne[M],head[N],tot=1;
	inline void add(int x,int y,int v,int c)
	{
		ver[++tot]=y; val[tot]=v; cost[tot]=c; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; cost[tot]=-c;ne[tot]=head[y]; head[y]=tot;
	}
	ll h[N],dis[N];
	bool vis[N];
	void spfa(int s,int t)
	{
		for(int i=0;i<=n;i++) h[i]=inf;
		queue<int> q;
		for(h[s]=0,q.push(s);!q.empty();)
		{
			int u=q.front(); q.pop();
			for(int i=head[u],v;i;i=ne[i])
				if(val[i]&&h[v=ver[i]]>h[u]+cost[i])
				{
					h[v]=h[u]+cost[i];
					if(!vis[v]) q.push(v),vis[v]=1;
				}
			vis[u]=0;
		}
	}
	struct node{
		int u; ll dis;
		friend inline bool operator<(const node &A,const node &B){return A.dis>B.dis;}
	};
	int pv[N],pe[N];
	priority_queue<node> q;
	ll MCMF()
	{
		spfa(s,t);
		int flow=0; ll co=0;
		for(;;)
		{
			for(int i=0;i<=n;i++) dis[i]=inf;
			for(dis[s]=0,q.push((node){s,dis[s]});!q.empty();)
			{
				node now=q.top(); q.pop();
				int u=now.u;
				if(dis[u]<now.dis) continue;
				for(int i=head[u],v;i;i=ne[i])
				if(val[i])
				{
					v=ver[i];
					if(dis[v]+h[v]>dis[u]+h[u]+cost[i])
						dis[v]=dis[u]+h[u]+cost[i]-h[v],
						q.push((node){v,dis[v]}),
						pv[v]=u,pe[v]=i;
				}
			}
			if(dis[t]==inf) break;
			for(int i=0;i<=n;i++) h[i]+=dis[i];
			int tmp=0x3fffffff;
			for(int u=t;u!=s;u=pv[u]) tmp=min(tmp,val[pe[u]]);
			flow+=tmp; co+=h[t]*tmp;
			for(int u=t,i;u!=s;u=pv[u]) i=pe[u],val[i]-=tmp,val[i^1]+=tmp;
		}
		return co;
	}
}
int n,m,K,dis[N][N],s,t;
int main()
{
	n=read(); m=read(); K=read();
	memset(dis,0x3f,sizeof(dis));
	fo(i,0,n) dis[i][i]=0;
	int x,y;
	fo(i,1,m) x=read(),y=read(),dis[x][y]=dis[y][x]=min(dis[x][y],read());
	fo(k,0,n) fo(i,0,n) fo(j,0,n)
		if((k<=i||k<=j)&&dis[i][j]>dis[i][k]+dis[k][j])
			dis[i][j]=dis[i][k]+dis[k][j];
	Graph::n=2*n+2; s=Graph::s=2*n+2; t=Graph::t=2*n+1;
	fo(i,1,n) Graph::add(s,i,1,0),Graph::add(i+n,t,1,0);
	Graph::add(s,0,K,0);
	fo(i,0,n) fo(j,i+1,n) Graph::add(i,j+n,1,dis[i][j]);
	printf("%lld\n",Graph::MCMF());
	return 0;
}