题意:在一副双向权值为正的图中，吴邪在1点，张起灵在n点，在吴邪到张起灵位子走最短路的情况下，张起灵想知道他最小破坏几条边，使得吴邪无法到达他这个点；吴邪想知道张起灵最多破坏多少条边使得自己还能到张起灵哪里。
思路：对于第一个问题，很明显是最小割，加边的处理因为是在最短路的情况下，所以只需要加最短路得边，跑一遍sap；
对于第二个问题，dijstra跑一下，对于k->i,如果lowcost[k]+cost[k][i]<lowcost[i],那这个就是最短路，那么len[i]=len[k]+1;如果lowcost[k]+cost[k][i]==lowcost[i]，那么len[i]=min(len[i],len[k]+1);问题的答案就是m-len[end];
代码：
#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
//const int MAXN = 100010;//點數的最大值
//const int MAXM = 400010;//邊數的最大值
const int INF = 0x3f3f3f3f;#define eps 1e-9
const int MAXN = 2200;//點數的最大值
const int MAXM = 240000;//邊數的最大值
//double a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值，求解之后x存的就是结果
int equ,var;//方程数和未知数个数
struct Edge
{int to,next,cap,flow;
}edge[MAXM];//注意是MAXM
int gap[MAXN],dep[MAXN],cur[MAXN],head[MAXN],tol,S[MAXN],n;
void init()
{tol = 0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0)
{edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;edge[tol].next = head[u]; head[u] = tol++;edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end)
{memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0] = 1;int front = 0, rear = 0;dep[end] = 0;Q[rear++] = end;while(front != rear){int u = Q[front++];for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(dep[v] != -1)continue;Q[rear++] = v;dep[v] = dep[u] + 1;gap[dep[v]]++;}}
}
int sap(int start,int end,int N )
{BFS(start,end);memcpy(cur,head,sizeof(head));int top = 0;int u = start;int ans = 0;while(dep[start] < N){if(u == end){int Min = INF;int inser;for(int i = 0;i < top;i++)if(Min > edge[S[i]].cap - edge[S[i]].flow){Min = edge[S[i]].cap - edge[S[i]].flow;inser = i;}for(int i = 0;i < top;i++){edge[S[i]].flow += Min;edge[S[i]^1].flow -= Min;}ans += Min;top = inser;u = edge[S[top]^1].to;continue;}bool flag = false;int v;for(int i = cur[u]; i != -1; i = edge[i].next){v = edge[i].to;if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){flag = true;cur[u] = i;break;}}if(flag){S[top++] = cur[u];u = v;continue;}int Min = N;for(int i = head[u]; i != -1; i = edge[i].next)if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){Min = dep[edge[i].to];cur[u] = i;}gap[dep[u]]--;if(!gap[dep[u]])return ans;dep[u] = Min + 1;gap[dep[u]]++;if(u != start)u = edge[S[--top]^1].to;}return ans;
}
int MIN(int a,int b){return a<b?a:b;}
int cost[MAXN][MAXN];
bool vis[MAXN];
int pre[MAXN];
int lowcost[MAXN];
int len[MAXN];
int flag[MAXN][MAXN];
void dijstra(int n,int beg)
{for(int i=0;i<n;i++){len[i]=INF;lowcost[i]=INF;vis[i]=false;pre[i]=-1;}len[0]=0;lowcost[beg]=0;for(int j=0;j<n;j++){int k=-1;int Min=INF;for(int i=0;i<n;i++){if(!vis[i]&&lowcost[i]<Min){Min=lowcost[i];k=i;}}if(k==-1) break;vis[k]=true;for(int i=0;i<=n;i++){if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){lowcost[i]=lowcost[k]+cost[k][i];pre[i]=k;len[i]=len[k]+1;//len[i]=min(len[i],len[k]+1);}else if(lowcost[k]+cost[k][i]==lowcost[i]){//lowcost[i]=lowcost[k]+cost[k][i];pre[i]=k;len[i]=min(len[i],len[k]+1);}}}//printf("%d\n",m-len[n-1]);
}
int main ()
{int u,v,w,m;while(scanf("%d %d",&n,&m)!=EOF){init();memset(flag,0,sizeof(flag));for(int i=0;i<n;i++)for(int j=0;j<n;j++)cost[i][j]=INF;//memset(cost,0x3f3f3f3f,sizeof(cost));for(int i=1;i<=m;i++){scanf("%d %d %d",&u,&v,&w);;u--,v--;if(cost[u][v]>w){cost[v][u]=w;cost[u][v]=w;flag[u][v]=1;flag[v][u]=1;}else if(cost[u][v]==w){flag[u][v]++;flag[v][u]++;}}dijstra(n,0);for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(lowcost[j]==lowcost[i]+cost[i][j])for(int ii=0;ii<flag[i][j];ii++)addedge(i,j,1);printf("%d %d\n",sap(0,n-1,n),m-len[n-1]);//printf("%d\n",dist[n-1]);}return 0;
}/*
6 8
1 2 1
1 2 3
1 3 4
2 4 4
2 5 4
3 5 1
4 6 2
5 6 16 9
1 3 4
1 2 1
1 2 3
1 3 4
2 4 4
2 5 4
3 5 1
4 6 2
5 6 16 9
5 6 1
1 2 1
1 2 3
1 3 4
2 4 4
2 5 4
3 5 1
4 6 2
5 6 1
*/