【题意】：给出一个无向图，边上的权值为通过这条边的时间。有四类点，分别代表客服的家，客服的办公室，客户的家和维修站，客服数量大于客户数量。现在要求对于每个客户都要有一个客服到达他的家然后再到达维修站，每个客服只能服务一个客户，最后所有的客服都要回到他们各自的办公室（有些客服是直接回办公室的）。问所有客服回到办公室的平均时间最少是多少。
【题解】：先用floyd预处理点到点的最短路。
然后设状态dp[i][j]表示第i个客服服务完第j个客户后回到自己的办公室的最短时间。
因为题目要求的是平均时间最少，也就是总时间最少。
可以想到用费用流模型：
源点s向每个客服连边，容量为1，费用为0；
每个客户向汇点t连边，容量为1，费用为0；
每个客服向每个客户连边，容量为1，费用为dp[i][j]；
增加一个虚拟结点x，表示有些客服是直接回办公室的。每个客服向s连边，容量为1，费用为每个人直接回办公室的时间。
可以想到，最后有r - c个客服直接回办公室，所以x连边到汇点t，容量为r-c，费用为0.
最后求最小费用流即为答案。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 550
26 #define maxm 500000
27 const int inf = 1 << 28;
28 int maz[maxn][maxn];
29 int dp[maxn][maxn];
30 int rr[maxn], cc[maxn], mm[maxn];
31 int office[maxn];
32 int n, m;
33 int R, C, M;
34 int ans, anscost, eh[maxn], tot, low[maxn], p[maxn], dist[maxn];
35 int S, T; //源，汇
36 struct Edge {
37 int u, v, cost, cap, flow, next;
38 } et[maxm];
39 bool visit[maxn];
40
41 bool spfa() {
42 queue<int> que;
43 memset(visit, false, sizeof (visit));
44 memset(p, -1, sizeof (p));
45 memset(low, 0, sizeof(low));
46 fill(&dist[0], &dist[maxn], inf);
47 visit[S] = true, low[S] = inf, dist[S] = 0;
48 que.push(S);
49 while (!que.empty()) {
50 int u = que.front();
51 que.pop();
52 visit[u] = false;
53 for (int i = eh[u]; i != -1; i = et[i].next) {
54 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
55 if (flow < cap && dist[u] + cost < dist[v]) {
56 dist[v] = dist[u] + cost;
57 p[v] = i; //注意，这里是 i
58 low[v] = min(low[u], cap - flow);
59 if (!visit[v]) {
60 visit[v] = true;
61 que.push(v);
62 }
63 }
64 }
65 }
66 return dist[T] != inf;
67 }
68
69 void costflow() {
70 ans = 0, anscost = 0;
71 while (spfa()) {
72 int x = p[T];
73 ans += low[T];
74 anscost += low[T] * dist[T];
75 while (x != -1) {
76 et[x].flow += low[T];
77 et[x^1].flow -= low[T];
78 et[x^1].cost = -et[x].cost;
79 x = p[et[x].u];
80 }
81 }
82 }
83
84 void add(int u, int v, int cost, int cap, int flow) {
85 Edge e = {u, v, cost, cap, flow, eh[u]};
86 et[tot] = e;
87 eh[u] = tot++;
88 }
89
90 void addedge(int u, int v, int cost, int cap) {
91 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
92 }
93
94 void init() {
95 tot = 0;
96 memset(eh, -1, sizeof (eh));
97 }
98
99 void floyd() {
100 for(int k = 1; k <= n; k++)
101 for(int i = 1; i <= n; i++)
102 for(int j = 1; j <= n; j++)
103 maz[i][j] = min(maz[i][j], maz[i][k] + maz[k][j]);
104 }
105
106 void solve() {
107 init();
108 floyd();
109 int X = R + C + 1;
110 S = 0, T = X + 1;
111 for(int i = 1; i <= R; i++) addedge(S, i, 0, 1);
112 for(int i = 1; i <= C; i++) addedge(R + i, T, 0, 1);
113 addedge(X, T, 0, R - C);
114 for(int i = 1; i <= R; i++) {
115 for(int j = 1; j <= C; j++) {
116 for(int k = 1; k <= M; k++)
117 dp[i][j] = min(dp[i][j], maz[rr[i]][cc[j]] + maz[cc[j]][mm[k]] + maz[mm[k]][office[i]]);
118 if(dp[i][j] < inf) addedge(i, j + R, dp[i][j], 1);
119 }
120 addedge(i, X, maz[rr[i]][office[i]], 1);
121 }
122 costflow();
123 double average = 1.0 * anscost / R;
124 average = ceil(average);
125 int aver = (int)average;
126 int hh = 8 + aver / 60;
127 int mins = aver % 60;
128 printf("%02d:%02d\n", hh, mins);
129
130 }
131
132 int main() {
133 int T;
134 scanf("%d", &T);
135 while(T--) {
136 scanf("%d%d", &n, &m);
137 for(int i = 1; i <= n; i++) {
138 for(int j = 1; j <= n; j++) {
139 maz[i][j] = inf;
140 dp[i][j] = inf;
141 }
142 maz[i][i] = 0;
143 }
144 for(int i = 0; i < m; i++) {
145 int a, b, c;
146 scanf("%d%d%d", &a, &b, &c);
147 maz[a][b] = maz[b][a] = c;
148 }
149 scanf("%d", &R);
150 for(int i = 1; i <= R; i++) scanf("%d%d", &rr[i], &office[i]);
151 scanf("%d", &C);
152 for(int i = 1; i <= C; i++) scanf("%d", &cc[i]);
153 scanf("%d", &M);
154 for(int i = 1; i <= M; i++) scanf("%d", &mm[i]);
155 solve();
156 }
157 return 0;
158 }
159