自动搬运

查看原文

来自洛谷，原作者为

	单曦增 这个家伙很不懒，什么也没有留下

搬运于2025-08-24 21:58:43，当前版本为作者最后更新于2018-06-29 17:50:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：给定一个无向图，删除某些边有一定的代价，要求删掉使得最短路径减小，求最小代价。

首先要spfa求出起点到各个点的最短距离。对于一条权值为w，起点为i，终点为j的边，设dis[k]为起点到k点的距离，若dis[j]=dis[i]+w，则将该边加入另一个图里，边的容量为删除这条边的代价，则从起点到终点的最大流即为答案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int inf=0x3fffffff;
const int Maxn=1100000;

int to[Maxn],nxt[Maxn],first[Maxn],t[Maxn],c[Maxn];
int w[Maxn],too[Maxn],nxtt[Maxn],firstt[Maxn];
int n,m,ti,co,u,v,tot=1,e[Maxn];
int b[Maxn],cur[Maxn],dis[Maxn];

inline void add(int u,int v,int ti,int co) {
    to[tot]=v;
    nxt[tot]=first[u];
    t[tot]=ti;
    c[tot]=co;
    first[u]=tot++;
}

inline void add(int u,int v,int wi) {
    too[tot]=v;
    w[tot]=wi;
    nxtt[tot]=firstt[u];
    firstt[u]=tot++;
}

void spfa() {
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(e,0,sizeof(e));
    q.push(1);
    dis[1]=0;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        e[now]=0;
        for(int i=first[now];i;i=nxt[i])
            if(dis[to[i]]>dis[now]+t[i]) {
                dis[to[i]]=dis[now]+t[i];
                if(e[to[i]]==0) {
                    q.push(to[i]);
                    e[to[i]]=1;
                }
            }
    }
}

bool bfs() {
    queue<int>q;
    q.push(1);
    memset(b,0,sizeof(b));
    b[1]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=firstt[now];i;i=nxtt[i])
            if(w[i]&&b[too[i]]==0) {
                b[too[i]]=b[now]+1;
                q.push(too[i]);
            }
    }
    return b[n];
}

int dfs(int root,int flow) {
    if(root==n) return flow;
    for(int &i=cur[root];i;i=nxtt[i])
        if(b[too[i]]==b[root]+1&&w[i]) {
            int temp=dfs(too[i],min(w[i],flow));
            if(temp) {
                w[i]-=temp;
                w[i^1]+=temp;
                return temp;
            }
        }
    return 0;
}

int dinic() {
    int ans=0,temp;
    while(bfs()) {
        memcpy(cur,firstt,sizeof(cur));
        while(temp=dfs(1,inf))
            ans+=temp;
    }
    return ans;
}

int main() {
   // freopen("test.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d%d",&u,&v,&ti,&co);
        add(u,v,ti,co);
        add(v,u,ti,co);
    }
    spfa();
    tot=2;
    for(int i=1;i<=n;i++)
        for(int j=first[i];j;j=nxt[j])
            if(dis[to[j]]==dis[i]+t[j]) {
                add(i,to[j],c[j]);
                add(to[j],i,0);
            }
    printf("%d\n%d\n",dis[n],dinic());
    return 0;
}