Problem Statement
坎格鲁斯普雷最近学了最短路有关的算法，于是他给袋鼠将军出了这样一个问题： 给定一张有 $n$ 个节点的图，图中初始没有任何边。然后给你 $m$ 条有权值的没有被指定连接的节点的（你可以任意决定它所连接的节点）无向边，你需要将这 $m$ 条无向边全部加进图内（每条边只能被使用一次），不允许出现自环（但允许出现重边），使得 1 号节点到其他所有节点的最短路恰好为一个给定的数组 $dis$。 袋鼠将军显然并不是图论高手，他并不会这道问题，于是他求助于你。当然，袋鼠将军也不是一个贪心的人，你并不需要构造问题的解决方案，你只需要判断问题是否有解即可。
本题包含多组测试数据 输入第一行一个整数 $T$，表示测试数据组数。$(1 \leq T \leq 500)$ 对于每组测试数据，第一行两个整数 $n, m$。$(1 \leq n, m \leq 500)$ 第二行 $m$ 个整数 $w_i$，表示第 $i$ 条边的权值。$(0 \leq w_i \leq 10^9)$ 第三行 $n$ 个整数 $dis_i$，表示题目给定的数组，$dis_i$ 表示 1 号节点到 $i$ 号节点的最短路长度。$(0 \leq dis_i \leq 10^9)$ 数据保证 $\sum n, \sum m$ 均不大于 $500$。
Output
对于每组测试数据，若有解，输出一行一个字符串 YES；若无解，输出一行一个字符串 NO。评测时不区分大小写，也就是说，YeS，yes，nO 都会被认为是正确的答案。
Solving
将dis数组排序，可以得到数值越大的dis一定是由数值小的转移得到的，此时我们可以将题目建模为一个类似于二分图匹配的问题，枚举dis间的差值，看看能把那些边权放入其中，建模节点与其连向该节点边的匹配，排除特判n == 1的情况，剩下的n-1个节点会匹配n-1条合适的边构成最短路，此时剩下的m - (n-1)条边，必须可以加在图中且不影响最短路径，我们可以在预处理时特判此种情况，如果最小的边权大于最小的DistanceGap，此时肯定无法填满这m条边，输出no即可；剩余情况，我们只需要将节点分为二分图左边的点，给边编号后分为二分图右边的点，连接两边点的边，根据是否存在恰好等于两点dis差值的边权建边，最后如果可以形成n-1个点的完美匹配，则证明有解
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
|
// 使用最大流Dinic算法求二分图的最大匹配
void solve()
{
int n,m;
cin >> n >> m;
vector<int> w(m+1);
for(int i=1;i<=m;i++) cin >> w[i];
vector<pii> dis(n+1);
for(int i=1;i<=n;i++) cin >> dis[i].first,dis[i].second = i;
sort(dis.begin()+1,dis.end());
if(dis[1].first != 0)
{
cout << "No\n";
return;
}
if(n == 1)
{
if(m > 0)
{
cout << "NO\n";
return;
}
else cout << "YES\n";
return;
}
int lo = INF;
for(int i=2;i<=n;i++) lo = min(lo,dis[i].first - dis[i-1].first);
//特判：要求必须使用所有 m 条边，如果存在 w[i] < lo 的边，它既不能用于构建最短路树，又不能作为额外边添加（会破坏最短路）
for(int i=1;i<=m;i++)
{
if(w[i] < lo)
{
cout << "NO\n";
return;
}
}
Flow<int> mf(n+m+200,n*m*2);
// 虚拟源点，虚拟汇点
int s = n + m + 1,t = n + m + 2; // node 1 ~ n,edge n + 1 ~ n + m
// 每个节点与前驱边匹配，能进行(n-1)节点数的完美匹配则代表有解
for(int i=2;i<=n;i++)
{
mf.addedge(s,dis[i].second,1);
}
for(int i=1;i<=m;i++)
{
mf.addedge(i+n,t,1);
}
map<int,vector<int>> group; // 存储差值为边权的组
for(int i=1;i<=m;i++)
{
group[w[i]].push_back(i+n); // 将同一边权的边的序号归为一组
}
for(int i=2;i<=n;i++)
{
set<int> diff;
for(int j=1;j<i;j++) // 枚举所有可能前驱节点
{
diff.insert(dis[i].first - dis[j].first);
}
for(auto d : diff) // 枚举差值
{
for(auto k : group[d])
{
mf.addedge(dis[i].second,k,1);
}
}
}
int flow = mf.maxflow(s,t);
if(flow == n - 1)
{
cout << "YES\n";
}
else cout << "NO\n";
}
|