题目描述
输入
输出
样例输入
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4
样例输出
5
提示
2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
合肥市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为上学需要的最短为正无穷大:这显然是一个合法的方案。
吐槽
这题各种单向边双向边变来变去,一会单向,一会双向,一会又单向添加两次,各种乱七八糟的,把我自己绕晕了。只是粗浅地搞懂原理,却没真正理解题目意思和解法真的不好啊!
解题思路
第一问单源最短路,才500个点,随便乱搞套各种模板的节奏,这里我选择了代码量极短的Floyd(后面求最小割即最大流时加边比spfa更方便)。
B2056洛谷、 然后第二问,要把所有最短路径都切断,那么我们用Floyd或其他spfa什么的跑出所有最短路构成的图,每条边的切割代价为c,那么求一波这个图的最小割,就是答案了(好像BZOJ 1002 狼抓兔子啊)。由于最小割等于最大流,所以我们在最短路图上跑最大流算法即可,这里我用的Dinic,蒟蒻版几乎无优化。
源代码
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m;struct Edge_road{int u,v,w,c; }g[130000]; int dis[510][510],num=1; inline void addg(int u,int v,int w,int c) {g[num++]={u,v,w,c};//不排序的前向星,只加单向边dis[u][v]=dis[v][u]=min(dis[u][v],w);//dis数组用来跑floyd,加双向边,有重边则选最小边长的一条边 } inline void floyd() {for(int i=1;i<=n;i++) dis[i][i]=0;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); }struct Edge_flow{int next,to,flow; }e[300010]; int cnt=2,head[510]={0}; inline void add(int u,int v,int c) {e[cnt]={head[u],v,c};head[u]=cnt++;e[cnt]={head[v],u,0};head[v]=cnt++; }int dep[510]={0}; bool bfs() {memset(dep,0,sizeof(dep));queue<int> q;dep[1]=1;q.push(1);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(!dep[v]&&e[i].flow){dep[v]=dep[u]+1;q.push(v);}}}return dep[n]!=0; }int dfs(int u,int f) {if(u==n||f==0) return f;int sum=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dep[v]==dep[u]+1&&e[i].flow){int delta=dfs(v,min(f-sum,e[i].flow));sum+=delta;e[i].flow-=delta;e[i^1].flow+=delta;if(f-sum<=0) break;}}if(!sum) dep[u]=-1;return sum; } int main() {scanf("%d%d",&n,&m);memset(dis,0x3f,sizeof(dis));memset(g,-1,sizeof(-1));for(int i=1,u,v,w,c;i<=m;i++){scanf("%d%d%d%d",&u,&v,&w,&c);addg(u,v,w,c);}floyd();printf("%d\n",dis[1][n]);for(int i=1;i<=m;i++){int u=g[i].u,v=g[i].v,w=g[i].w,c=g[i].c;if(dis[1][u]+w+dis[v][n]==dis[1][n]) add(u,v,c);if(dis[1][v]+w+dis[u][n]==dis[1][n]) add(v,u,c);//如果这条边在最短路上,就加到最短路图中}int ans=0;while(bfs()){while(int temp=dfs(1,0x7fffffff))ans+=temp;}printf("%d\n",ans);return 0; }