「BZOJ3258」秘密任务 - 最小割唯一性判定 | Bill Yang's Blog

「BZOJ3258」秘密任务 - 最小割唯一性判定

题目大意

    Alice听说在一片神奇的大陆MagicLand,有一个古老的传说……
    很久很久以前,那个时候 MagicStates共和国刚刚成立。 反对新政府的势力虽已被镇压,但仍然在暗地活动。这一次,情报局得到了一个令人震惊的消息,被软禁在首都府邸中的Frank ——著名的反对派领袖,秘密逃出首都,去往反对派的大本营。根据相关的情报,Frank计划通过城市之间 发达的高速公路,经过最短的路程抵达目的地。不妨将 MagicStates共和国简化为由$N$个城市,$M$条高速公路构成的连通的无向图,首都为城市$1$,反对派的大本营为城市$N$。
    每条高速公路连接两个不同的城市,且路程是已知的。而Frank选择了一条从城市$1$到城市$N$的最短路径作为他的逃跑路线。为了阻止Frank,共和国总统决定在某些城市的高速公路的出入口设立检查点,在Frank经过检查点时将他逮捕。
    举例来说,如果有一条高速公路连接城市$u$和城市$v$,在这条公路的城市$u$或城市$v$的出入口设立检查点,那么Frank经过高速公路时就会被发现。特别的是,由于城市$N$实际上处在反对派的控制下,所以不能在城市$N$设立检查点。
    然而在任何城市设立检查点都需要一定的费用。更具体的,若在城市$u$设立$k$个检查点,就要花费$A_u$乘以$k$的代价,其中$A_u$是城市$u$的相关参数。值得注意的是,这个代价与这$k$个检查点具体设在哪些公路的出入口无关,于是,总统责令情报局拟定一个方案,花费最小的代价使得无论Frank选择哪条最短路线,都会在(除城市$N$以外)某个城市的高速公路出入口被发现。读到这里,Alice很想知道阻止Frank所需要花费的最小代价,并且她还希望知道最优方案是否是唯一的。只好再请你帮助她了。
    注意,我们称两个方案不同当且仅当存在某城市$k$,两种方案中在城市$k$的检查点的设置(而不仅是数目)是不同的。
    注意,输入文件包含多组测试数据。


题目分析

先跑两次最短路将网络流图建出来。
注意每条边需要拆点,因为这条边可以割两个位置,且影响唯一性。
然后跑一次最小割。

接下来需要做的是判定最小割的唯一性。
以前的方法是用两次DFS判断S集合与T集合是否有交集。
然而这道题有重边,因此不能使用这种方法,下面我们来考虑新的方法。

必要(关键)割边

在最小割集中必定出现的边称为必要割边,或关键割边。
判定关键割边的方法:
若可以分别从$S,T$到达$a,b$,则$a\rightarrow b$为关键割边。
正确性是显然的。

可能割边

在最小割集中可能出现的边称为可能割边。
判定可能割边的方法:
将残余网络用Tarjan缩点,若一条正向边跨越不同强连通分量且满流,则其为可能割边。
正确性:这条边连通两个强连通分量,且有流量,说明流量可以且必须通过此边到达T,又因为满流,因此必定能够找到一个割集包含此边。

最小割唯一性判定

有了以上两个定义,我们就可以判定最小割的唯一性了。
若所有的可能割边都是必要割边,则最小割唯一。
将残余网络用Tarjan缩点,若一条正向边跨越不同强连通分量且满流,且不刚好跨越$S,T$所在强连通分量,则最小割不唯一。

然后就可以完成此题了。


代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=4505;

struct Edge {int from,to,dist;};

int n,m,top=0,step=0,BCC=0,cnt=0,a[maxn],Belong[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn];
LL dist1[maxn],dist2[maxn];
bool vst[maxn],Instack[maxn];
vector<Edge> edges[maxn];

void Clear() {
step=BCC=0;
for(int i=1; i<=cnt; i++) {
edges[i].clear();
Dfn[i]=0;
}
}

#define pii pair<LL,int>

void Dijkstra(int s,LL *dist) {
fill(dist,dist+n+1,LLONG_MAX/2),fill(vst,vst+n+1,0);
priority_queue<pii,vector<pii>,greater<pii> > Q;
Q.push(pii(dist[s]=0,s));
while(!Q.empty()) {
int Now=Q.top().second;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(Edge &e:edges[Now]) {
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
Q.push(pii(dist[Next],Next));
}
}
}
}

struct Dinic {
struct Edge {
int from,to;
LL cap,flow;
Edge(int x=0,int y=0,LL c=0,LL f=0):from(x),to(y),cap(c),flow(f) {}
};
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
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,LL v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
fill(vst+1,vst+n+1,0);
queue<int> Q;
Q.push(t); //reversed
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
if(Next==s)return 1;
Q.push(Next);
}
}
}
return vst[s];
}
LL dfs(int Now,LL a) {
if(Now==t||a==0)return a;
LL flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
LL nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
LL maxflow(int s,int t) {
this->s=s;
this->t=t;
LL flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,LLONG_MAX);
}
return flow;
}
} dinic;

void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int id:dinic.G[Now]) {
auto &e=dinic.edges[id];
if(e.flow==e.cap)continue;
int Next=e.to;
if(!Dfn[Next]) {Tarjan(Next);Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);}
else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
BCC++;
int y;
do {
y=Stack[top--];
Belong[y]=BCC;
Instack[y]=0;
} while(y!=Now);
}
}

int main() {
int t=Get_Int();
while(t--) {
Clear();
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++)a[i]=Get_Int();
a[n]=INT_MAX;
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
edges[x].push_back((Edge) {x,y,v});
edges[y].push_back((Edge) {y,x,v});
}
Dijkstra(1,dist1);
Dijkstra(n,dist2);
dinic.init(cnt);
cnt=n;
for(int Now=1; Now<n; Now++)
for(Edge &e:edges[Now]) {
int Next=e.to;
if(dist1[n]==dist1[Now]+e.dist+dist2[Next]) {
cnt++; //!!!
dinic.AddEdge(Now,cnt,a[Now]);
dinic.AddEdge(cnt,Next,a[Next]);
}
}
dinic.n=cnt;
LL ans=dinic.maxflow(1,n);
for(int i=1; i<=cnt; i++)if(!Dfn[i])Tarjan(i);
bool bj=1;
for(auto &e:dinic.edges) {
int x=e.from,y=e.to;
if(!e.cap||e.cap!=e.flow||Belong[x]==Belong[y]||(Belong[x]==Belong[1]&&Belong[y]==Belong[n]))continue;
printf("No %lld\n",ans);
bj=0;
break;
}
if(bj)printf("Yes %lld\n",ans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~
0%