「dwjshift毒瘤模拟赛」path - 平面图最短路转最小割 (毒瘤,未AC) | Bill Yang's Blog

「dwjshift毒瘤模拟赛」path - 平面图最短路转最小割 (毒瘤,未AC)

题目大意

    给出一个包含$n+1$个结点的有向图,结点的编号为$0$到$n$。图中有$m$条有向边,第$i$条有向边起点为$u_i$,终点为$v_i$,且长度为$w_i$。并且这些边还满足如下的性质:

  • 对任意一条边,满足 $u_i\lt v_i$。
  • 不存在两条边$i,j$使得$u_i<u_j<v_i<v_j$。除了结点$0$和结点$n$以外,其余的每个结点都有颜色。现在需要你找出一条从结点$0$走到结点$n$的最短路径。对于任意一种颜色,这条路径要么经过了这种颜色的所有结点,要么就不经过这种颜色的任意一个结点。如果不存在这样的路径,请输出$-1$,否则输出最短路径的长度。

题目分析

因为题目保证不存在$u_i<u_j<v_i<v_j$,故这是一个平面图。
带有这种限制的最短路很不好做,考虑转成对偶图最小割。

先把不可能经过的点删掉,样例二长这个样子。

然后把不可能完全经过的颜色全部删掉。
剩下的如图是一棵树。
每个对偶图上的点管辖其树上的后代所不管辖原图上的点。
割哪条边就走哪条边。
注意树上要连反向INF边表示不能割了父亲再割儿子。

怎么限制颜色呢?
每个对偶图的点向其管辖的原图点对应的“颜色点”连INF双向边。

原题题解部分是错的,原题数据第一组是错的。
也不知道我哪儿写错了,除开第一组持续80分。


代码

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
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX/3
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=2005;
struct Dinic {
struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int 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,int v1,int v2) {
edges.push_back(Edge(x,y,v1,0));
edges.push_back(Edge(y,x,v2,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);
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];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int 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;
int 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;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
} dinic;
struct Edge {
int from,to,dist;
Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
bool operator < (const Edge &b) const {return from<b.from||(from==b.from&&to>b.to);}
} edge[maxn],tmp[maxn];
vector<int> edges[maxn],fedges[maxn];
int n,m,a[maxn],Max=0;
bool vst1[maxn],vst2[maxn],del[maxn];
void Dfs1(int Now) {
vst1[Now]=1;
for(int Next:edges[Now])if(!vst1[Next])Dfs1(Next);
}
void Dfs2(int Now) {
vst2[Now]=1;
for(int Next:fedges[Now])if(!vst2[Next])Dfs2(Next);
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++)a[i]=Get_Int(),Max=max(Max,a[i]);
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
tmp[i]=Edge(x,y,v);
edges[x].push_back(y);
fedges[y].push_back(x);
}
Dfs1(0);
Dfs2(n);
for(int i=1; i<=n; i++)if(!vst1[i]||!vst2[i])del[a[i]]=1;
int tot=0;
for(int i=1; i<=m; i++)if(!del[a[tmp[i].from]]&&!del[a[tmp[i].to]])edge[++tot]=tmp[i];
m=tot;
edge[++m]=Edge(0,n,0);
sort(edge+1,edge+m+1);
int S=1,T=m+Max+1;
dinic.init(T);
for(int i=1; i<=m; i++) {
int last=edge[i].from,j=i+1;
while(true) {
while(edge[j].from<last&&j<=m)j++;
if(j>m||edge[j].to>edge[i].to)break;
dinic.AddEdge(i,j,edge[j].dist,inf);
last=edge[j].to;
if(last!=edge[i].to) {
dinic.AddEdge(i,m+a[last],inf,inf);
dinic.AddEdge(m+a[last],i,inf,inf);
}
}
if(last==edge[i].from)dinic.AddEdge(i,T,inf,0);
}
int ans=dinic.maxflow(S,T);
printf("%d\n",ans==inf?-1:ans);
return 0;
}
0%