[bzoj] 3258: 秘密任务

发表于   |   分类于   |  

题意

这题描述很复杂 .. 就不概括了

Alice听说在一片神奇的大陆MagicLand，有一个古老的传说……
很久很久以前，那个时候 MagicStates共和国刚刚成立。 反对新政府的势力虽已被镇压，但仍然在暗地活动。这一次，情报局得到了一个令人震惊的消息，被软禁在首都府邸中的Frank ——著名的反对派领袖，秘密逃出首都，去往反对派的大本营。根据相关的情报，Frank计划通过城市之间 发达的高速公路，经过最短的路程抵达目的地。不妨将 MagicStates共和国简化为由N个城市,M条高速公路构成的连通的无向图，首都为城市1，反对派的大本营为城市N。
每条高速公路连接两个不同的城市，且路程是已知的。而Frank选择了一条从城市1到城市N的最短路径作为他的逃跑路线。为了阻止Frank，共和国总统决定在某些城市的高速公路的出入口设立检查 点，在Frank经过检查点时将他逮捕。
举例来说，如果有一条高速公路连接城市u和城市v，在这条公路的城市u或城市v的出入口设立检查点，那么Frank经过高速公路时就会被发现。特别的是，由于城市N实际上处在反对派的控制下，所以不能在城市N设立检查点。

然而在任何城市设立检查点都需要一定的费用。更具体的，若在城市 u设立k个检查点，就要花费 Au乘以k的代价，其中Au是城市u的相关参数。值得注意的是，这个代价与这k个检查点具体设在哪些公路的出入口无关,于是，总统责令情报局拟定一个方案，花费最小的代价使得无论Frank选择哪条最短路线，都会在（除城市N以外）某个城市的高速公路出入口被发现。读到这里，Alice很想知道阻止Frank所需要花费的最小代价，并且她还希 望知道最优方案是否是唯一的。只好再请你帮助她了。
注意，我们称两个方案不同当且仅当存在某城市k，两种方案中在城市 k的检查点的设置（而不仅是数目）是不同的。
注意，输入文件包含多组测试数据。

传送门

分析

1>首先,不考虑判定唯一解时,显然我们需要将$1\to n$的最短路网求出来,在这个最短路网上考虑.
很容易发现我们只需要求一个最小割就时第二问.其中边$(u,v)$边权为$min(A[u],A[v])$

2>下面考虑怎样判断最小割是唯一的.
你真的只在想”最小割是否唯一”这个问题吗?那你就大错特错了我会告诉你我考试的时候就一直这么想的吗?渣渣
“最小割是否唯一”这个问题解决的并不是全部.
思考这种情况一条边$(u,v)$,$A[u]=A[v]$,这时即使最小割唯一,但是因为我们实际设置检查点的时候既可以在$u$也可以在$v$,会导致解的不唯一.若最小割唯一,我们就可以再枚举一遍被割掉的边两端的$A$值是否相等即可.

代码

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
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <cstring>
#include <deque>
#include <algorithm>

typedef long long ll ;

#define  maxn  510LL
#define  maxN  510LL
#define  maxM  5010LL
#define  infi  0x3f3f3f3f3f3f3f3fLL

struct FST { int to , next ; ll flow ; } e[maxM<<1] , e0[maxM<<1] ;
int star[maxN] , tote ;
int star0[maxN] , tote0 ;
inline void FST_init() {
truememset(star , 0 , sizeof star) ; tote = 1 ;
truememset(star0 , 0 , sizeof star0) ; tote0 = 0 ;
}
inline void AddEdge(int u , int v , ll cap) {
truee[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ;
truee[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}
inline void AddEdge0(int u , int v , ll w) {
truee0[++tote0].to = v ; e0[tote0].flow = w ; e0[tote0]. next = star0[u] ; star0[u] = tote0 ;
}

#define min(x,y)  std::min(x,y)
int N , S , T ;
int h[maxN] , vh[maxN] ;

ll dfs(int u , ll flowu) {
int p , tmp = h[u]+1 ;
ll flow = 0 , flowv ;
trueif (u == T) return flowu ;
truefor (p = star[u] ; p ; p = e[p].next) {
truetrueif (e[p].flow && (h[e[p].to]+1==h[u])) {
truetruetrueflowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
truetruetrueflow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
truetruetrueif (flow==flowu || h[S]==N) return flow ;
truetrue}
true}
truefor (p = star[u] ; p ; p = e[p].next)
truetrueif (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
trueif (--vh[h[u]] == 0) h[S] = N ;
trueelse ++ vh[h[u]=tmp+1] ;
truereturn flow ;
}

ll SAP() {
truell ret = 0 ;
truememset(vh , 0 , sizeof vh) ;
truememset(h , 0 , sizeof h) ;
truevh[S] = N ;
truewhile (h[S] < N) ret += dfs(S , infi) ;
truereturn ret ;
}

int Time ;
ll A[maxn] = {0} ;
ll dist[2][maxn] = {0} ;
bool inq[maxn] = {0} ;
bool chos[maxn] = {0} ;
std::deque<int>q;

void SPFA(int u , int o) {
int p , v ;
true#define dis(u)  dist[o][u]
truedis(u) = 0 ;
trueq.clear();
trueq.push_back(u) ;
truewhile (!q.empty()) {
truetrueu = q.front() , q.pop_front() , inq[u] = false ;
truetruefor (p=star0[u];p;p=e0[p].next) {
truetruetruev = e0[p].to ;
truetruetrueif (dis(v) > dis(u)+e0[p].flow) {
truetruetruetruedis(v) = dis(u)+e0[p].flow ;
truetruetruetrueif (!inq[v]) {
truetruetruetruetrueinq[v] = true ;
truetruetruetruetrueif (!q.empty() && dis(v)<dis(q.front())) q.push_front(v) ;
truetruetruetruetrueelse q.push_back(v) ;
truetruetruetrue}
truetruetrue}
truetrue}
true}
}

int n ;
ll sum , ans ;
int vis[maxn] = {0} ;
void dfss(int u,int i) {
truevis[u] = i+1 ;
truefor (int p=star[u];p;p=e[p].next)
        if(!vis[e[p].to] && e[p^i].flow)
            dfss(e[p].to,i) ;
}

bool judge() {
int i , j , p ;
truesum = 0 ;
truedfss(S,0) ;
truedfss(T,1) ;
trueRep (i,1,n-1) if (vis[i] == 1)
true    for (p=star[i];p;p=e[p].next) {
truetruetruej = e[p].to ;
truetruetrueif (!(p&1) && vis[e[p].to]==2) {
truetruetruetrueif (A[i] == A[j]) return false ;
truetruetruetrueelse sum += min(A[i],A[j]) ;
truetruetrue}
truetrue}
truereturn (sum == ans) ;
}

int main() {
int Time , u , v , m , i ;ll w ;
true#define READ
true#ifdef  READ
truetruefreopen("secret.in" ,"r",stdin ) ;
truetruefreopen("secret.out","w",stdout) ;
true#endif
trueread(Time) ;
truewhile (Time --> 0) {
truetrueread(n) , read(m) ;
truetrueFST_init() ;
truetrueRep (i,1,n-1) read(A[i]) ;
truetrueA[n] = infi ;
truetruememset(dist , 0x3f , sizeof dist) ;
truetrueRep (i,1,m) {
truetruetrueread(u) , read(v) , read(w) ;
truetruetrueAddEdge0(u,v,w) ;
truetruetrueAddEdge0(v,u,w) ;
truetrue}
truetrueSPFA(1,0) ;
truetrueSPFA(n,1) ;
truetrueRep (i,1,n)
truetruetrueif (dist[0][i]+dist[1][i] == dist[0][n]) chos[i] = true , vis[i] = false ;
truetruetrueelse chos[i] = false ;
truetrueRep (i,1,n)
truetrue    for (int p=star0[i];p;p=e0[p].next) {
truetruetruetrueint j = e0[p].to ;
truetruetruetrueif (chos[i] && chos[j]) {
truetruetruetruetrueif (dist[0][i]+dist[1][j]+e0[p].flow == dist[0][n]) {
truetruetruetruetruetrueAddEdge(i,j,min(A[i],A[j])) ;
truetruetruetruetrue}
truetruetruetrue}
truetruetrue}
truetrueS = 1 , T = N = n ;
truetrueans = SAP() ;
truetrueif (judge()) printf("Yes ") ;
truetrueelse printf("No ") ;
truetrueprintf("%lld\n", ans) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章