大意:最少炸掉多少个公交站就能让士兵无法在指定的K分钟内从源点到达汇点,即在有向图中删除几个点,使得源点到汇点的最短距离大于k。
介绍几个概念:
独立轨:网络中的非汇源点称为内点,而源点和内点的两两无公共点的内点的路径称为独立轨,可以用最小割理论证明。最小割定理有了新解释,那就是在网络中选择一个最小的内点集合并删去,使得源汇之间的所有独立轨都被破坏。
思路:只要想办法把所有长度小于K的独立轨破坏掉即可。这一题实际上求的是有向图的独立轨的数目,即有向图的顶点连通度,只不过有一个额外的要求,即独立轨的长度必须小于K才行,我们通过Floyd预处理一下,如果S->顶点->T的长度小于k的话,那么就可以连一条边。求独立轨的具体的操作是拆点,把A拆为A' A'',每个点A'->A''连一条容量为1的边, 对于边<u,v>而言,其中u'''->v'连一条容量为INF的边,然后以s'',t'求最大流即可。
求无向图的独立轨的方法见我另一篇博客:http://blog.csdn.net/wall_f/article/details/8212776
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 10010; const int MAXM = 400010; const int INF = 0x3f3f3f3f; struct Edge { int v, f; int next; }edge[MAXM]; int n, m, k; int cnt; int s, t; int first[MAXN], level[MAXN]; int d[MAXN][MAXN]; int x[MAXN], y[MAXN]; void init() { cnt = 0; memset(first, -1, sizeof(first)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = (i == j)? 0:INF; } } } void Floyd() { for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) if(d[i][k] != INF) for(int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } void read_graph(int u, int v, int f) { edge[cnt].v = v, edge[cnt].f = f; edge[cnt].next = first[u], first[u] = cnt++; edge[cnt].v = u, edge[cnt].f = 0; edge[cnt].next = first[v], first[v] = cnt++; } int bfs(int s, int t) { int q[MAXN]; memset(level, 0, sizeof(level)); level[s] = 1; int front = 0, rear = 1; q[front] = s; while(front < rear) { int x = q[front++]; if(x == t) return 1; for(int e = first[x]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(!level[v] && f) { level[v] = level[x] + 1; q[rear++] = v; } } } return 0; } int dfs(int u, int maxf, int t) { if(u == t) return maxf; int ret = 0; for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(level[v] == level[u] + 1 && f) { int Min = min(maxf-ret, f); f = dfs(v, Min, t); edge[e].f -= f; edge[e^1].f += f; ret += f; if(ret == maxf) return ret; } } return ret; } int Dinic(int s, int t) { int ans = 0; while(bfs(s, t)) ans += dfs(s, INF, t); return ans; } int read_case() { init(); scanf("%d%d%d", &n, &m, &k); if(!n && !m && !k) return 0; for(int i = 1; i <= m; i++) { scanf("%d%d", &x[i], &y[i]); d[x[i]][y[i]] = 1; } Floyd(); for(int i = 1; i <= n; i++) read_graph(i, i+n, 1); //A'->A''容量为1 for(int i = 1; i <= m; i++) { if(d[1][x[i]] + d[y[i]][n] < k) //长度小于K的独立轨 { read_graph(x[i]+n, y[i], INF); } } return 1; } void solve() { s = 1+n, t = n; int ans = Dinic(s, t); //A'', B' printf("%d\n", ans); } int main() { while(read_case()) { solve(); } return 0; }