Description
Gabiluso is one of the greatest spies in his country. Now he’s trying to complete an “impossible” mission ----- to make it slow for the army of City Colugu to reach the airport. City Colugu has n bus stations and m roads. Each road connects two bus stations directly, and all roads are one way streets. In order to keep the air clean, the government bans all military vehicles. So the army must take buses to go to the airport. There may be more than one road between two bus stations. If a bus station is destroyed, all roads connecting that station will become no use. What’s Gabiluso needs to do is destroying some bus stations to make the army can’t get to the airport in k minutes. It takes exactly one minute for a bus to pass any road. All bus stations are numbered from 1 to n. The No.1 bus station is in the barrack and the No. n station is in the airport. The army always set out from the No. 1 station. No.1 station and No. n station can’t be destroyed because of the heavy guard. Of course there is no road from No.1 station to No. n station. Please help Gabiluso to calculate the minimum number of bus stations he must destroy to complete his mission.
Input
There are several test cases. Input ends with three zeros. For each test case: The first line contains 3 integers, n, m and k. (0< n <=50, 0< m<=4000, 0 < k < 1000) Then m lines follows. Each line contains 2 integers, s and f, indicating that there is a road from station No. s to station No. f.
Output
For each test case, output the minimum number of stations Gabiluso must destroy.
题目大意：有n（n≤50）个点，起点1到终点n，有m条有向边（m≤4000）。现破坏掉若干起点和终点以外的点，使得从起点到终点经过的边数必须大于k条。问最少要破坏多少个点，保证从起点到终点没有边。
我们先来看一个可以AC但实际上错误的思路o(╯□╰)o（为什么错误还能AC啊？数据弱呗……）
思路：先求每个点到起点和终点的最短路径，然后每个点拆成两个点x、x'，如果dis(s,x) + dis(x,t) ≤ k，那么建一条边x→x'，容量为1（源点和汇点容量为无穷大）。对每条边(i, j)，连一条边i'→j，容量为无穷大。求最小割。根据最大流最小割定理，最大流为答案。因为对于一点x，如果dis(s,x) + dis(x,t) ＞ k，那么没必要破坏点x。那么问题就变成了最少破坏多少个点，使得从1到n必须要经过一个点，经过那个点的话从1到n必然会大于k。
先上代码（15MS）：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int MAXN = 210; 8 const int MAXE = 20010; 9 const int INF = 0x3fff3fff; 10 11 struct SAP { 12 int head[MAXN], cur[MAXN], pre[MAXN], gap[MAXN], dis[MAXN]; 13 int to[MAXE], cap[MAXE], flow[MAXE], next[MAXE]; 14 int ecnt, n, st, ed; 15 16 void init() { 17 memset(head, 0, sizeof(head)); 18 ecnt = 2; 19 } 20 21 void add_edge(int u, int v, int c) { 22 to[ecnt] = v; cap[ecnt] = c; flow[ecnt] = 0; next[ecnt] = head[u]; head[u] = ecnt++; 23 to[ecnt] = u; cap[ecnt] = 0; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++; 24 //printf("%d->%d %d\n", u, v, c); 25 } 26 27 void bfs() { 28 memset(dis, 0x3f, sizeof(dis)); 29 queue que; que.push(ed); 30 dis[ed] = 0; 31 while(!que.empty()) { 32 int u = que.front(); que.pop(); 33 ++gap[dis[u]]; 34 for(int p = head[u]; p; p = next[p]) { 35 int v = to[p]; 36 if(dis[v] > n && cap[p ^ 1]) { 37 dis[v] = dis[u] + 1; 38 que.push(v); 39 } 40 } 41 } 42 } 43 44 int Max_flow(int ss, int tt, int nn) { 45 st = ss, ed = tt, n = nn; 46 int ans = 0, minFlow = INF, u; 47 for(int i = 0; i <= n; ++i) { 48 cur[i] = head[i]; 49 gap[i] = 0; 50 } 51 u = pre[st] = st; 52 bfs(); 53 while(dis[st] < n) { 54 bool flag = false; 55 for(int &p = cur[u]; p; p = next[p]) { 56 int v = to[p]; 57 if(cap[p] > flow[p] && dis[v] + 1 == dis[u]) { 58 flag = true; 59 minFlow = min(minFlow, cap[p] - flow[p]); 60 pre[v] = u; 61 u = v; 62 if(u == ed) { 63 ans += minFlow; 64 while(u != st) { 65 u = pre[u]; 66 flow[cur[u]] += minFlow; 67 flow[cur[u] ^ 1] -= minFlow; 68 } 69 minFlow = INF; 70 } 71 break; 72 } 73 } 74 if(flag) continue; 75 int minDis = n - 1; 76 for(int p = head[u]; p; p = next[p]) { 77 int v = to[p]; 78 if(cap[p] > flow[p] && dis[v] < minDis) { 79 minDis = dis[v]; 80 cur[u] = p; 81 } 82 } 83 if(--gap[dis[u]] == 0) break; 84 gap[dis[u] = minDis + 1]++; 85 u = pre[u]; 86 } 87 return ans; 88 } 89 } G; 90 91 struct SP { 92 int head[MAXN], head2[MAXN], dis_st[MAXN], dis_ed[MAXN]; 93 int to[MAXE], next[MAXE], to2[MAXE], next2[MAXE]; 94 int ecnt, n, st, ed; 95 96 void init(int ss, int tt, int nn) { 97 memset(head, 0, sizeof(head)); 98 memset(head2, 0, sizeof(head2)); 99 ecnt = 2;100 st = ss; ed = tt; n = nn;101 }102 103 void add_edge(int u, int v) {104 to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt;105 to2[ecnt] = u; next2[ecnt] = head2[v]; head2[v] = ecnt++;106 }107 108 void make_dis_st() {109 memset(dis_st, 0x3f, sizeof(dis_st));110 queue que; que.push(st);111 dis_st[st] = 0;112 while(!que.empty()) {113 int u = que.front(); que.pop();114 for(int p = head[u]; p; p = next[p]) {115 int v = to[p];116 if(dis_st[v] > n) {117 dis_st[v] = dis_st[u] + 1;118 que.push(v);119 }120 }121 }122 }123 124 void make_dis_ed() {125 memset(dis_ed, 0x3f, sizeof(dis_ed));126 queue que; que.push(ed);127 dis_ed[ed] = 0;128 while(!que.empty()) {129 int u = que.front(); que.pop();130 for(int p = head2[u]; p; p = next2[p]) {131 int v = to2[p];132 if(dis_ed[v] > n) {133 dis_ed[v] = dis_ed[u] + 1;134 que.push(v);135 }136 }137 }138 }139 140 void make_G(int k) {141 make_dis_st();142 //for(int i = 1; i <= n; ++i) printf("%d ", dis_st[i]);143 make_dis_ed();144 //for(int i = 1; i <= n; ++i) printf("%d ", dis_ed[i]);145 G.init();146 G.add_edge(1, 1 + n, INF);147 G.add_edge(n, n + n, INF);148 for(int i = 2; i < n; ++i)149 if(dis_st[i] + dis_ed[i] <= k) G.add_edge(i, i + n, 1);150 for(int u = 1; u <= n; ++u) {151 for(int p = head[u]; p; p = next[p]) {152 int v = to[p];153 G.add_edge(u + n, v, INF);154 }155 }156 }157 } T;158 159 int n, m, k, a, b;160 161 int main() {162 while(scanf("%d%d%d", &n, &m, &k) != EOF) {163 if(n == 0 && m == 0 && k == 0) break;164 T.init(1, n, n);165 while(m--) {166 scanf("%d%d", &a, &b);167 T.add_edge(a, b);168 }169 T.make_G(k);170 printf("%d\n", G.Max_flow(1, n + n, n + n));171 }172 }
但是这样做是错的，为什么呢？我们来看一个Discuss里的数据：
8 10 5
1 22 33 44 55 66 81 77 84 77 4这个数据输出应该是1（破坏点7），但是上面的代码会输出2。因为上面的思路忽略了一点：当我们破坏掉某个点的时候，经过另一些从起点到终点的距离可能会变化以至于大于k。
那么怎么办呢？我们只能退而求其次o(╯□╰)o，虽然这也是一个能AC但是错的思路
思路：每个点拆成两个点x、x'（还是拆点╮(╯▽╰)╭），然后建一条边x→x'，容量为1（源点和汇点为无穷大），费用为0。然后对每条边(i, j)建一条边，容量为无穷大，费用为1。那么不断增广直到费用大于k时停止增广，这是流量就是答案（还是求流╮(╯▽╰)╭）。
上代码（46MS）：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int MAXN = 222; 8 const int MAXE = 10010; 9 const int INF = 0x3f3f3f3f;//can't modify10 11 int n, m, k, a, b;12 13 struct MinCostFlow {14 bool vis[MAXN];15 int head[MAXN], dis[MAXN], pre[MAXN];16 int to[MAXE], next[MAXE], cost[MAXE], flow[MAXE];17 int n, st, ed, ecnt;18 19 void init(int ss, int tt, int nn) {20 memset(head, 0, sizeof(head));21 ecnt = 2;22 st = ss, ed = tt, n = nn;23 }24 25 void add_edge(int u, int v, int c, int f) {26 to[ecnt] = v; cost[ecnt] = f; flow[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;27 to[ecnt] = u; cost[ecnt] = -f; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++;28 }29 30 bool spfa() {31 memset(vis, 0, sizeof(vis));32 memset(dis, 0x3f, sizeof(dis));33 queue que; que.push(st);34 vis[st] = true; dis[st] = 0;35 while(!que.empty()) {36 int u = que.front(); que.pop();37 vis[u] = false;38 for(int p = head[u]; p; p = next[p]) {39 int v = to[p];40 if(flow[p] && dis[v] > dis[u] + cost[p]) {41 dis[v] = dis[u] + cost[p];42 pre[v] = p;43 if(!vis[v]) {44 vis[v] = true;45 que.push(v);46 }47 }48 }49 }50 return dis[ed] <= k;51 }52 53 void min_cost_flow(int &minFlow, int &fee) {54 minFlow = fee = 0;55 while(spfa()) {56 fee += dis[ed];57 int u = ed, tmp = INF;58 while(u != st) {59 tmp = min(tmp, flow[pre[u]]);60 u = to[pre[u] ^ 1];61 }62 u = ed;63 while(u != st) {64 flow[pre[u]] -= tmp;65 flow[pre[u] ^ 1] += tmp;66 u = to[pre[u] ^ 1];67 }68 minFlow += tmp;69 }70 }71 72 int mincost() {73 int ret, tmp;74 min_cost_flow(tmp, ret);75 return ret;76 }77 78 int maxflow() {79 int ret, tmp;80 min_cost_flow(ret, tmp);81 return ret;82 }83 } G;84 85 86 int main() {87 while(scanf("%d%d%d", &n, &m, &k) != EOF) {88 if(n == 0 && m == 0 && k == 0) break;89 G.init(1, n * 2, n * 2);90 G.add_edge(1, 1 + n, INF, 0);91 G.add_edge(n, n + n, INF, 0);92 for(int i = 2; i < n; ++i) G.add_edge(i, i + n, 1, 0);93 while(m--) {94 scanf("%d%d", &a, &b);95 G.add_edge(a + n, b, INF, 1);96 }97 printf("%d\n", G.maxflow());98 }99 }
10 11 5
1 2
2 33 44 55 102 91 66 77 88 99 10然后上面的代码就过不了这组数据o(╯□╰)o，代码输出1，正确输出为2，怪不得我想不明白为什么是对的o(╯□╰)o（这数据敢不敢再弱一点……）
最后我们只能再退而求其次了o(╯□╰)o，暴力枚举答案，然后枚举最短路径上的点，深搜，再枚举删点后最短路径上的点，再深搜……
搜索（484MS，慢了点但起码是对了╮(╯▽╰)╭）：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int MAXN = 110; 8 const int MAXE = 4010; 9 const int INF = 0x3fff3fff;10 11 int n, m, k, a, b, ans, ecnt;12 int SP[MAXN][MAXN];13 int head[MAXN], dis[MAXN], pre[MAXN];14 int to[MAXE], next[MAXE];15 bool del[MAXN];16 17 void init() {18 memset(head, 0, sizeof(head));19 memset(del, 0, sizeof(del));20 ecnt = 2;21 }22 23 void add_edge(int u, int v) {24 to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;25 }26 27 bool bfs() {28 memset(dis, 0x3f, sizeof(head));29 queue que; que.push(1);30 dis[1] = 0;31 while(!que.empty()) {32 int u = que.front(); que.pop();33 for(int p = head[u]; p; p = next[p]) {34 int v = to[p];35 if(!del[v] && dis[v] > n) {36 dis[v] = dis[u] + 1;37 pre[v] = u;38 if(v == n) return dis[n] <= k;39 que.push(v);40 }41 }42 }43 return false;44 }45 46 bool flag;47 48 void dfs(int dep) {49 if(!bfs()) {50 flag = true;51 return ;52 }53 if(dep > ans) return ;54 int u = pre[n], cnt = 0;55 while(u != 1) {56 SP[dep][cnt++] = u;57 u = pre[u];58 }59 for(int i = cnt - 1; i >= 0; --i) {60 del[SP[dep][i]] = true;61 dfs(dep + 1);62 del[SP[dep][i]] = false;63 }64 }65 66 int main() {67 while(scanf("%d%d%d", &n, &m, &k) != EOF) {68 if(n == 0 && m == 0 && k == 0) break;69 init();70 while(m--) {71 scanf("%d%d", &a, &b);72 add_edge(a, b);73 }74 flag = false;75 for(ans = 0; ans < n; ++ans) {76 dfs(1);77 if(flag) break;78 }79 printf("%d\n", ans);80 }81 }