隐藏
「SDOI2010」星际竞速 - 路径覆盖/二分图 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SDOI2010」星际竞速 - 路径覆盖/二分图

题目大意

    $n$个星球,$m$个带权有向边构成DAG。从任意位置瞬移到星球$i$花费$A_i$代价。第一次选择星球必须瞬移,要访问每个星球恰好一次,求最小总代价。


题目分析

类似最小路径覆盖的建图。
因为仅覆盖整个地图一次,路径可以拆为若干条相互独立的边,故按照最小路径覆盖的建图方式拆分。
对于能力爆发模式,它和高速航行模式相互独立,故直接从源点到对应出点连边。
跑mcmf得答案。


代码

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
132
133
134
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=5005;

struct Edge {
int from,to,cap,flow,cost;
Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct zkw_CostFlow {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn],vst[maxn];
int a[maxn],path[maxn];
LL dist[maxn];
int flow;
LL cost;
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v,int f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool spfa() {
for(int i=1; i<=n; i++)dist[i]=LLONG_MAX/2;
memset(inque,0,sizeof(inque));
dist[t]=0;
inque[t]=1;
deque<int>Q;
Q.push_back(t);
while(!Q.empty()) {
int Now=Q.front();
Q.pop_front();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(dist[Next]>dist[Now]+e.cost&&e.cap>e.flow) {
dist[Next]=dist[Now]+e.cost;
if(!inque[Next]) {
inque[Next]=1;
if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next);
else Q.push_back(Next);
}
}
}
}
return dist[s]<LLONG_MAX/2;
}
int dfs(int Now,int a) {
if(vst[Now])return 0;
if(Now==t||a==0)return a;
int flow=0;
vst[Now]=1;
for(int id:G[Now]) {
Edge& e=edges[id];
int Next=e.to;
if(dist[Now]-e.cost!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
cost+=(LL)nextflow*e.cost;
e.flow+=nextflow;
edges[id^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
flow=cost=0;
while(spfa()) {
memset(vst,0,sizeof(vst));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} zkw;

int n,m;
int main() {
n=Get_Int();
m=Get_Int();
int S=2*n+2,T=2*n+3;
zkw.init(2*n+5);
for(int i=1; i<=n; i++) {
zkw.AddEdge(S,i,1,0); //每个点只经过一次(只能往引力大的走)
zkw.AddEdge(n+i,T,1,0);
zkw.AddEdge(S,n+i,1,Get_Int()); //能力爆发模式:直接到达出点
}
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),c=Get_Int();
if(x>y)swap(x,y);
zkw.AddEdge(x,n+y,1,c);
}
zkw.maxflow(S,T);
printf("%lld\n",zkw.cost);
return 0;
}
姥爷们赏瓶冰阔落吧~