此题第一问最短路即可。主要是第二问。
第二问求最小的删除边的方案使得1到n的最短路变大。
最小的删除让我们想到了最小割。
然而最小割是使得1到n不连通。
于是我们把最短路图抽出来跑最小割。
一条边（x，v）当dis[x]+val[i]==dis[v]时说明这是最短路图中的一条边。
#include<bits/stdc++.h> #define LL long long #define N 200003 #define M 125000 #define INF 2100000000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct EDEG{ int nextt,to,t,c,me; }w[M*2],w2[M*2]; int head[N],head2[N],cur[N]; int vis[N],dis[N]; struct qnode{ int v,c; qnode(int _v=0,int _c=0):v(_v),c(_c){} bool operator <(const qnode &r)const { return r.c<c; } }; int n,m; int tot=0,tot2=1; void add(int a,int b,int t,int c) { tot++; w[tot].nextt=head[a]; w[tot].me=a; w[tot].t=t; w[tot].c=c; w[tot].to=b; head[a]=tot; } void add2(int a,int b,int c) { tot2++; w2[tot2].nextt=head2[a]; w2[tot2].c=c; w2[tot2].to=b; head2[a]=tot2; } priority_queue<qnode>q; void dij()//处理第一问 { while(!q.empty())q.pop(); for(int i=1;i<=n;++i)vis[i]=0,dis[i]=INF; dis[1]=0; q.push(qnode(1,0)); while(!q.empty()) { int x=q.top().v;q.pop(); if(vis[x])continue; vis[x]=1; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(!vis[v]&&dis[x]+w[i].t<dis[v]) { dis[v]=dis[x]+w[i].t; q.push(qnode(v,dis[v])); } } } } queue<int>qq; bool bfs() { memset(dis,0,sizeof(dis));//这里就将就用dis数组不再另开一个 while(!qq.empty())qq.pop(); qq.push(1);dis[1]=1; while(!qq.empty()) { int x=qq.front();qq.pop(); for(int i=head2[x];i;i=w2[i].nextt) { int v=w2[i].to; if(w2[i].c&&!dis[v]) { qq.push(v); dis[v]=dis[x]+1; if(v==n)return 1; } } } return 0; } int dinic(int x,int flow) { if(x==n)return flow; int rest=0; for(int &i=cur[x];i;i=w2[i].nextt) { int v=w2[i].to; if(w2[i].c&&dis[v]==dis[x]+1) { int k=dinic(v,min(flow-rest,w2[i].c)); rest+=k; w2[i].c-=k;w2[i^1].c+=k; if(rest==flow)return rest; } } return rest; } void min_cut() { int flow=0,maxflow=0; while(bfs()) { for(int i=1;i<=n;++i)cur[i]=head2[i]; while(flow=dinic(1,INF))maxflow+=flow; } printf("%d\n",maxflow); } int main() { n=read();m=read(); for(int i=1;i<=m;++i) { int a=read(),b=read(); int t=read(),c=read(); add(a,b,t,c);add(b,a,t,c); } dij(); printf("%d\n",dis[n]); for(int i=1;i<=tot;++i) if(dis[w[i].me]+w[i].t==dis[w[i].to])//说明在最短路图中 add2(w[i].me,w[i].to,w[i].c),add2(w[i].to,w[i].me,0); min_cut(); }