题意：给你n个墓室，m条路径，一个人在1号墓室（起点），另一个人在n号墓室（终点），起点的那个人只有通过最短路径才能追上终点的那个人，而终点的那个人能切断任意路径。
第一问——终点那人要使起点那人不能追上的情况下可以切的最少的路径数，输出最少的路径数
第二问——起点那人能追上终点那人的情况下，终点那人能切断的最多的路径数，输出最多的路径数
我们先用dijstra计算出最短距离 然后通过最短距离建边 建成每条边容量为1 的 网络流 然后再求这个图的最大流 最大流等于最小割 因为我们知道了 最短路是个GAD 然后我们直接再找一次便可
#include <iostream> #include <algorithm> #include <string.h> #include <cstdio> #include <vector> #include <queue> using namespace std; const int INF=2147483647; const int maxn=2000+5; struct Dinic{ struct Edge{ int from,to,cap,flow; Edge(int cfrom, int cto , int ccap, int cflow) { from=cfrom; to=cto; cap=ccap;flow=cflow; } }; int n,m,s,t; vector<Edge>edges; vector<int>G[maxn]; int d[maxn]; int cur[maxn]; void init(int n) { this->n=n; edges.clear(); for(int i=0; i<=n; i++)G[i].clear(); } void AddEdge(int from,int to, int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(d,-1,sizeof(d)); queue<int>Q; Q.push(s); d[s]=0; while(!Q.empty()) { int x =Q.front(); Q.pop(); for(int i=0; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if((d[e.to]==-1)&&e.cap>e.flow){ d[e.to]=d[x]+1; Q.push(e.to); } } } return d[t]!=-1; } int DFS(int x, int a) { if(x==t || a<=0)return a; int flow=0,f; for(int &i=cur[x]; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } int Maxflow(int s, int t) { this->s=s; this->t=t; int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(s,INF-8); } return flow; } }; struct Dijskstr { struct Edge { int from,to,dist; Edge(int cfrom, int cto, int cdist) { from=cfrom; to=cto; dist=cdist; } }; struct HeapNode { int d,u; bool operator <(const HeapNode &rhs) const{ return d>rhs.d; } HeapNode(int cd ,int cu) { d=cd; u=cu; } }; int dis[maxn]; int n,m; vector<Edge>edges; vector<int>G[maxn]; bool done[maxn]; int d[maxn]; void init(int n) { this->n=n; for(int i=0; i<=n; i++)G[i].clear(); edges.clear(); } void AddEdge(int from , int to, int dist) { edges.push_back(Edge(from,to,dist)); m=edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<HeapNode>Q; for(int i=0; i<=n; i++)d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); Q.push(HeapNode(0,s)); while(!Q.empty()) { HeapNode x=Q.top(); Q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0; i<G[u].size(); i++) { Edge &e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; Q.push(HeapNode(d[e.to],e.to)); } } } } Dinic dic; int solve() { for(int i=0; i<=n; i++)dis[i]=INF; queue<int>Q; Q.push(1); dis[1]=0; dic.init(n); while(!Q.empty()) { int x= Q.front();Q.pop(); int siz=G[x].size(); for(int i=0; i<siz; i++) { Edge &e=edges[G[x][i]]; if(d[e.to]==d[x]+e.dist){ dic.AddEdge(x,e.to,1); dis[e.to]=min(dis[e.to],dis[x]+1); Q.push(e.to); } } } return dic.Maxflow(1,n); } }dij; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { if(n==1){ while(true); } dij.init(n); for(int i=0; i<m; i++) { int a,b,li; scanf("%d%d%d",&a,&b,&li); dij.AddEdge(a,b,li); dij.AddEdge(b,a,li); } dij.dijkstra(1); if(dij.d[n]==INF){ while(true); } int d2=dij.solve(); printf("%d %d ",d2,m-dij.dis[n]); } return 0; }