【题意】:给出一个无向图,边上的权值为通过这条边的时间。有四类点,分别代表客服的家,客服的办公室,客户的家和维修站,客服数量大于客户数量。现在要求对于每个客户都要有一个客服到达他的家然后再到达维修站,每个客服只能服务一个客户,最后所有的客服都要回到他们各自的办公室(有些客服是直接回办公室的)。问所有客服回到办公室的平均时间最少是多少。

【题解】:先用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<intint> 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, falsesizeof (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