情报 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 28(5 users)Total Accepted: 1(1 users)Rating: Special Judge: No Description
A国和B国是同盟国，战争之际，A国的一个城市获取了敌方的一个有利情报，并且已经迅速的转达给了A国的每个城市，现在A国首领想要把这个情报转达给B国的每个城市。
由于情报十分机密，A国的每个城市只能派出一名情报员将消息转达给B国的一个城市，之后必须迅速返回，每个A国城市只能派出情报员一次，并且B国内部城市之间不能相互通信。A国首领想知道采取最优的策略后，B国每个城市都获得情报所需的最少时间是多少。
Input
多组测试数据。
对于每组测试数据，第一行输入一个K表示城市的总个数，城市的编号为1~K。（2≤K≤100）
接下来的K行每行K个整数，第 i 行第 j 个数表示从 i 城市到 j 城市所需要的时间（每个整数不超过100）。
接下来输入一个N表示A国城市的个数。
接下来一行输入N个整数，表示A国城市的编号。
接下来输入一个M表示B国城市的个数。
接下来一行输入M个整数，表示B国城市的编号。（N≥M）
Output对于每组数据输出一个整数表示B国每个城市获得情报所需要的最少时间，每组输出占一行。
Sample Input 2 0 1 1 0 1 2 1 1 3 0 2 1 2 0 10 1 10 0 2 2 3 1 1 Sample Output 1 1 Author `Wind @hrbust 思路：
题目标称是错的，别想着Ac了。
首先用Floyd跑出最短路。
然后二分最终时间，那么对于小于等于这个二分时间的边进行建边。
然后跑最大匹配，如果最大匹配==m.那么记录最终可行解，继续二分（减小r）.否则增加l.
这题差评的理由：
http://acm.hrbust.edu.cn/index.php?m=Discuss&a=showDiscuss&thread_id=12739
我的代码：
http://paste.ubuntu.com/24151661/.
搞到的能够Ac的代码：
#include <cstdio> #include <cstring> const int MAXN = 205, INF = 99999999; int n1, n2; int m1[MAXN], m2[MAXN]; int mat[MAXN][MAXN]; bool mk[MAXN]; bool dfs(int u) { for (int i = 0; i < n2; ++i) { if (mat[u][i] && !mk[i]) { mk[i] = true; if (m2[i] == -1 || dfs(m2[i])) { m2[i] = u; m1[u] = i; return true; } } } return false; } int maxmatch() { int ret = 0; memset(m1, -1, sizeof(m1[0])*n1); memset(m2, -1, sizeof(m2[0])*n2); for (int i = 0; i < n1; ++i) { if (m1[i] == -1) { memset(mk, 0, sizeof(mk[0]) * n2); if (dfs(i)) ++ret; } } return ret; } int g[MAXN][MAXN]; int va[MAXN], vb[MAXN]; int k, n, m; int check(int mid) { memset(mat, 0, sizeof(mat)); n1 = n, n2 = m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (g[ va[i] ][ vb[j] ] <= mid) { mat[i][j] = 1; } } } return maxmatch() == m; } int main() { while (EOF != scanf("%d", &k)) { for (int i = 0; i < k; ++i) { for (int j = 0; j < k; ++j) { scanf("%d", &g[i][j]); } } for (int a = 0; a < k; ++a) { for (int i = 0; i < k; ++i) { for (int j = 0; j < k; ++j) { if (g[i][j] > g[i][a] + g[a][j]) { g[i][j] = g[i][a] + g[a][j]; } } } } scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &va[i]); va[i]--; } scanf("%d", &m); for (int i = 0; i < m; ++i) { scanf("%d", &vb[i]); vb[i]--; } int l = 0, r = 100; while (l < r) { int mid = l + (r - l) / 2; if (check(mid)) { r = mid; } else { l = mid + 1; } } printf("%d\n", l); } return 0; }
