hdu6582

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

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

1、首先最短路径一定在最短路图上

2、如果起点和终点不联通，就不存在这样一条最短路径，所以最短路径一定会变大；

注意看范围。。wa17发

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<queue>

using namespace std;

typedef long long ll;

const ll INF=1e18;

const int M=1e4+;

struct node{

    ll u,v,nextt;

    ll w;

}g[M<<],e[M<<];

ll s,t,tot1,tot2,cur[M],head1[M],head2[M],vis[M],deep[M];

ll dis[M];

void addedge1(ll u,ll v,ll w){

    g[tot1].u=u;

    g[tot1].v=v;

    g[tot1].w=w;

    g[tot1].nextt=head1[u];

    head1[u]=tot1++;

}

void addedge2(ll u,ll v,ll w){

    e[tot2].v=v;

    e[tot2].w=w;

    e[tot2].nextt=head2[u];

    head2[u]=tot2++;

    e[tot2].v=u;

    e[tot2].w=;

    e[tot2].nextt=head2[v];

    head2[v]=tot2++;

}

void dij(){

    for(int i=;i<=t;i++)

        dis[i]=INF;

//    cout<<"!!"<<endl;

    queue<int>que;

    que.push(s);

    dis[s]=;

    while(!que.empty()){

        ll  u=que.front();

        que.pop();

        vis[u]=;

        for(ll i=head1[u];~i;i=g[i].nextt){

            ll v=g[i].v;

            if(dis[v]>dis[u]+g[i].w){

                dis[v]=dis[u]+g[i].w;

                if(!vis[v]){

                    vis[v]=;

                    que.push(v);

                }

            }

        }

    }

}

ll dd[M];

bool bfs(){

    memset(deep,,sizeof(deep));

    queue<int>que;

    que.push(s);

    deep[s]=;

    while(!que.empty()){

        int u=que.front();

        que.pop();

        for(int i=head2[u];i!=-;i=e[i].nextt){

            int v=e[i].v;

            if(e[i].w>&&deep[v]==){

                deep[v]=deep[u]+;

                if(v==t)

                    return true;

                que.push(v);

            }

        }

    }

    return deep[t]==?false:true;

}

ll dfs(ll u,ll fl){

    if(u==t)

        return fl;

    ll ans=,x=;

    for(int i=cur[u];i!=-;i=e[i].nextt){

        ll v=e[i].v;

        if(e[i].w>&&deep[v]==deep[u]+){

            x=dfs(v,min(e[i].w,fl-ans));

            e[i].w-=x;

            e[i^].w+=x;

            if(e[i].w)

                cur[u]=i;

            ans+=x;

            if(ans==fl)

                return ans;

        }

    }

    if(ans==)

        deep[u]=;

    return ans;

}

ll dinic(){

    ll ans=;

    while(bfs()){

        for(int i=;i<=t;i++)

            cur[i]=head2[i];

        ans+=dfs(s,INF);

    }

    return ans;

}

int main(){

    ll test;

    scanf("%lld",&test);

    while(test--){

        ll n,m;

        tot1=tot2=;

        scanf("%lld%lld",&n,&m);

    //    cout<<tot1<<"!!"<<tot2<<endl;

        s=,t=n;

        for(int i=;i<=n;i++)

            head1[i]=head2[i]=-,vis[i]=;

        while(m--){

            ll u,v;

            ll w;

            scanf("%lld%lld%lld",&u,&v,&w);

            addedge1(u,v,w);

        }

        dij();

    //    for(int i=1;i<=n;i++)

    //        cout<<dis[i]<<endl;

         for (int i = ; i <= n; i++)

             for (int j = head1[i]; ~j;j = g[j].nextt)

                 if (dis[g[j].u] + g[j].w == dis[g[j].v])

                    addedge2(g[j].u,g[j].v,g[j].w);

        printf("%lld\n",dinic());

    }

    return ;

}