hdu 5294 Tricks Device题目大意：吴邪在古墓中追张起灵，古墓中有很多条路，走每条路都需要一个时间，吴邪只有在最短的时间从古墓的入口到达出口才能追上张起灵。但是张起灵很厉害，他可以使用奇门遁甲使一条路无法通行。现在，问，张起灵最少堵住几条路就可以使吴邪追不上他，以及在吴邪可以追上张起灵的情况下，张起灵最多能堵多少条路。解题思路：先求出古墓中的最短路（耗时最少的路），再求最短路的同时，记录走最短路要通过哪几条路和走最短路最少通过的路数。最多能堵住的路就是总的路数减去走最短路所要走过的最少的路数。然后根据最短路经过的路，来建网络流的图，求出的最大流，，就是最少需要堵住的路。;ll;const int INF = 0x3f3f3f3f;const int N = 20005;int n, m, s, t;struct EdgeS {int from, to, dist; }; vector<EdgeS> edgesS; vector<int> GS[N];int visS[N], dS[N], rec[N];void initS() {memset(visS, 0, sizeof(visS));for (int i = 0; i < N; i++) GS[i].clear();edgesS.clear(); } void addEdgeS(int from, int to, int dist) {edgesS.push_back((EdgeS){from, to, dist});edgesS.push_back((EdgeS){to, from, dist});int pos = edgesS.size();GS[from].push_back(pos – 2);GS[to].push_back(pos – 1);} void SPFA() {memset(visS,0,sizeof(visS));for (int i = 0; i < N; i++) dS[i] = INF;for (int i = 0; i < N; i++) rec[i] = INF;dS[s] = 0;rec[s] = 0;visS[s] = 1;queue<int> Q;Q.push(s);while (!Q.empty()) {int u = Q.front();Q.pop();visS[u] = 0;for (int i = 0; i < GS[u].size(); i++) {int v = edgesS[GS[u][i]].to;if (dS[v] > dS[u] + edgesS[GS[u][i]].dist) {dS[v] = dS[u] + edgesS[GS[u][i]].dist;rec[v] = rec[u] + 1;if (!visS[v]) {visS[v] = 1;Q.push(v);}} else if (dS[v] == dS[u] + edgesS[GS[u][i]].dist) {if (rec[v] > rec[u] + 1) {rec[v] = rec[u] + 1;if (!visS[v]) {visS[v] = 1;Q.push(v);}}}}} } struct Edge{int from, to, cap, flow; };vector<Edge> edges;vector<int> G[N];void init() {for (int i = 0; i < N; i++) G[i].clear();edges.clear();}void addEdge(int from, int to, int cap, int flow) {edges.push_back((Edge){from, to, cap, 0});edges.push_back((Edge){to, from, 0, 0});int m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);} int vis[N], d[N];int BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;Q.push(s);d[s] = 0;vis[s] = 1;while (!Q.empty()) {int u = Q.front(); Q.pop();for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (!vis[e.to] && e.cap > e.flow) {vis[e.to] = 1;d[e.to] = d[u] + 1;Q.push(e.to);}}}return vis[t];}int cur[N];int DFS(int u, int a) {if (u == t || a == 0) return a;int flow = 0, f;for (int &i = cur[u]; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (d[u] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap – e.flow))) > 0) {e.flow += f;edges[G[u][i]^1].flow -= f;flow += f;a -= f;if (a == 0) break;}}return flow;}int MF() { //dinic算法求最大流int ans = 0;while (BFS()) {memset(cur, 0, sizeof(cur));ans += DFS(s, INF);}return ans;}int main() {while (scanf(“%d %d”, &n, &m) == 2) {int u, v, d;s = 0, t = n – 1;init();initS();for (int i = 0; i < m; i++) {scanf(“%d %d %d”, &u, &v, &d);if (u == v) continue;addEdgeS(u – 1, v – 1, d);}SPFA();for (int i = 0; i < edgesS.size(); i++) {if (dS[edgesS[i].to] == dS[edgesS[i].from] + edgesS[i].dist) {addEdge(edgesS[i].from, edgesS[i].to, 1, 0);}}printf(“%d %d\n”, MF(), m – rec[n – 1]);}return 0;}
靠山山会倒，靠人人会跑，只有自己最可靠。
