题目链接
题目大意：给出一个无向图，每条边有长度和代价。求出1到n的最短路。删掉一些边使得1到n的最短路变大并使得删掉边的代价之和最小。
题解：跑出最短路树，然后求最短路树上的最小割
我的收获：按照3931改了几行就过了……
#include <iostream> #include <cstdio> #include <cstring> #include <climits> #include <algorithm> using namespace std; const int M=2005; const int MM=133333; #define ll long long #define INF LLONG_MAX/10000 int n,m,t,t2,st,ed; int lim[M],head[M],last[M],num[M],d[M]; int head2[M],q[MM]; ll dis[M]; bool vis[M],Exit; struct node{int fr,to,nex;ll val,cost;}p[MM*4]; struct edge{int to,nex;ll c;}e[MM*4]; void add2(int u,int v,ll w,ll co){p[t2].fr=u,p[t2].to=v,p[t2].val=w,p[t2].cost=co,p[t2].nex=head2[u],head2[u]=t2++;} void add(int u,int v,ll w){e[t].to=v,e[t].c=w,e[t].nex=head[u],last[u]=head[u]=t++;} void insert(int u,int v,ll w){add(u,v,w),add(v,u,0);} ll dfs(int x,ll in) { if(x==ed) return in; ll ans=0,f; for(int i=last[x];i!=-1;last[x]=i=e[i].nex) { int v=e[i].to; if(e[i].c&&d[v]==d[x]-1){ f=dfs(v,min(in-ans,e[i].c)); ans+=f; e[i].c-=f; e[i^1].c+=f; if(Exit||ans==in) return ans; } } if(--num[d[x]]==0) Exit=1; d[x]++,num[d[x]]++,last[x]=head[x]; return ans; } void build() { t=0;memset(head,-1,sizeof(head)); for(int i=0;i<t2;i++) if(dis[p[i].fr]+p[i].val==dis[p[i].to]) insert(p[i].fr,p[i].to,p[i].cost); } void work() { Exit=0; ll flow=0; while(!Exit) flow+=dfs(st,INF); cout<<dis[n]<<endl<<flow<<endl; } void spfa(int x){ for(int i=1;i<=n;i++) dis[i]=INF; int h=0,w=0;q[++w]=1,dis[1]=0,vis[1]=true; while(h<w){ int u=q[++h];vis[u]=false; for(int i=head2[u];i!=-1;i=p[i].nex){ int v=p[i].to; if(dis[v]>dis[u]+p[i].val){ dis[v]=dis[u]+p[i].val; if(!vis[v]) vis[v]=true,q[++w]=v; } } } } void init() { int x,y,z,zz;t2=0; cin>>n>>m;memset(head2,-1,sizeof(head)); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&x,&y,&z,&zz),add2(x,y,z,zz),add2(y,x,z,zz); st=1,ed=n,num[0]=n;spfa(1); build(); } int main() { init(); work(); return 0; }